Устройство управляемой перестановки информации, хранимой в эвм

Устройство управляемой перестановки информации, хранимой в эвм

Иллюстрации

Показать все

Реферат

Устройство относится к области преобразования информации и может быть использовано в вычислительной технике, системах коммуникации и защиты информации от несанкционированного доступа.

Для задач, связанных с преобразованием форматов данных методом перестановок, необходимы высокоскоростные устройства, осуществляющие перестановку входных данных под управлением внешних кодов. Наибольший интерес представляют однотактные устройства, осуществляющие заданную перестановку за один такт внешнего генератора тактовых импульсов. В этом случае частое изменение управляющих кодов не должно приводить к замедлению работы устройства.

Известен дешифратор управляемой побитовой транспозиции информации, хранимой в персональной ЭВМ (см. патент РФ №2320000, МПК G06F 7/76). Дешифратор содержит К уровней узлов дешифрации, каждый уровень дешифрации содержит 2ⁱ элементов , регистр управляющих кодов, сдвиговый регистр данных, двойной буферный регистр накопления и хранения форматированных данных, блок управления, генератор тактовых импульсов. Вход выборки дешифратора соединен с первыми входами первого и второго элементов первого уровня. Элемент первого уровня реализует логическую функцию , остальные элементы реализуют логическую функцию . Вход Х элемента первого уровня соединен с выходом первого бита регистра управляющих кодов, входы X₁ остальных элементов i-го уровня соединены с выходом i-ro бита регистра управляющих кодов, входы X₂ остальных элементов i-ro уровня соединены с выходами элементов i-1 уровня, причем вход двойного буферного регистра накопления и хранения форматированных данных соединен с выходом сдвигового регистра данных, а входы разрешения записи этого регистра соединены с выходами последнего уровня дешифрации. Генератор тактовых импульсов соединен с блоком управления, который своими входами и выходами соединен с буферным регистром накопления и хранения форматированных данных, входным сдвиговым регистром данных, регистром управляющих кодов.

Недостатком данного дешифратора является последовательное преобразование данных, которое происходит за N тактовых импульсов генератора, что при больших значениях N значительно снижает быстродействие.

Известны сортирующие сети Бетчера ("Sorting Networks and Their Applications", К.E.Batcher, Proceedings of 1968 Spring Joint Computer Conference, pp.307-314, 1968). Данные устройства осуществляют быструю сортировку 2^p элементов данных за 1/2р(1+р) шагов, но не обеспечивают перестановку данных, управляемую внешним кодом.

Известна модифицированная сеть Бетчера для сортировки несортированных входных сигналов за log₂N последовательных проходов. Сеть строится рекурсивно от размера 4 до произвольного размера. Модифицированная сеть Бетчера сортирует N элементов данных за log₂N последовательных проходов через сеть, где N - число элементов данных для каждого прохода. Сеть имеет задержку на log₂N компараторах (см. патент US №5319788, МПК G06F 7/36; G06F 7/22).

Однако данная сеть не обеспечивает управляемую внешним кодом перестановку входных данных.

Известно устройство для осуществления управляемых перестановок, которое состоит из двух сетей типа «Butterfly» одинакового размера, соединенных одна с другой (back-to-back). Управление осуществляется программно с помощью процессора.

Недостатком данного устройства является программное управление перестановками, которое осуществляется процессором и приводит к замедлению работы системы (см. патент US №6922472, МПК H04L 9/34).

Задачей настоящего решения является упрощение и ускорение процесса управления перестановками при минимизации элементов устройства.

Техническим результатом является возможность высокоскоростного параллельного преобразования форматов блоков данных методом перестановок с использованием управляющих кодов.

Поставленная задача достигается тем, что устройство управляемой перестановки информации, хранимой в ЭВМ, с n входами и n выходами управляющих кодов, n входами и n выходами данных включает в себя сортирующую сеть, каждая ячейка которой состоит из компаратора сортирующей сети, с двумя входами, двумя выходами и выходом управления, который соединен с входом управления транспозиционного элемента ячейки, имеющего два входа и два выхода данных, причем для пар ячеек, компараторы которых соединены между собой в соответствии с топологией сортирующей сети, выполняется условие, если выход компаратора первой ячейки соединен с входом компаратора второй ячейки, то вход транспозиционного элемента первой ячейки соединен с выходом транспозиционного элемента второй ячейки, входы управляющих кодов устройства образованы входами компараторов входных ячеек сортирующей сети, а выходы управляющих кодов устройства образованы выходами компараторов выходных ячеек сортирующей сети, входы данных образованы входами транспозиционных элементов выходных ячеек сортирующей сети, а выходы данных образованы выходами транспозиционных элементов входных ячеек сортирующей сети.

Изобретение поясняется чертежами, где на фиг.1 приведена блок-схема устройства, на фиг.2 приведена схема для реализации управляемой перестановки вектора данных из 4 элементов на основе сортирующей сети Бетчера,

где

1. устройство управляемой перестановки;

2. ячейки сортирующей сети;

Х1, Х2,…, Хn - n входов данных;

Y1, Y2,…, Yn - n выходов данных;

IC1, IC2,…, IСn - n входов управляющих кодов;

ОС1, ОС2,…, ОСn-n выходов управляющих кодов;

π(1,2,…, n) - перестановка управляющих кодов;

(1,2,…, n) - отсортированные управляющие коды;

(x₁, х₂,…, х_n) - входные данные;

π(х₁, х₂,…, х_n) - выходные данные;

X₁, X₂ - первый и второй входы данных транспозиционных элементов;

Y1, Y₂ - первый и второй выходы данных транспозиционных элементов;

IC₁, IC₂ - первый и второй входы компараторов;

OC₁, OC₂ - первый и второй выходы компараторов;

IC1, IC2, IC3, IC4 - входы управляющих кодов;

OC1, OC2, ОС3, ОС4 - выходы управляющих кодов;

X1, Х2, Х3, Х4 - входы данных;

Y1, Y2, Y3, Y4 - выходы данных.

Предлагаемое устройство включает в себя сортирующую сеть 1, в узлах которой находятся ячейки 2, состоящие из компаратора сортирующей сети и транспозиционного элемента управляемой перестановки данных. Компаратор сортирующей сети имеет управляющий выход (на чертежах не показан), два входа IC₁, IC₂ и два выхода OC₁, OC₂. Транспозиционный элемент имеет вход управления, входы X₁, Х₂ и выходы Y₁, Y₂. В каждой ячейке управляющий выход компаратора соединен с входом управления транспозиционного элемента.

Соединения выходов OC₁ и входов IC₁, выходов ОС₂ и входов IC₂ компараторов определяются топологией используемой сортирующей сети. Соединения IC1,IC2,…, ICn входов управляющих кодов с входами компараторов входных ячеек сортирующей сети определяются топологией используемой сортирующей сети. Соединения ОС1,ОС2,…, ОСn выходов управляющих кодов с выходами компараторов выходных ячеек сортирующей сети определяются топологией используемой сортирующей сети.

Если выход ОС₁ компаратора одной ячейки сортирующей сети соединен с входом IC₁ компаратора другой ячейки сортирующей сети, то вход X₁ транспозиционного элемента одной ячейки соединен с выходом Y₁ другой ячейки. Если выход ОС₂ компаратора одной ячейки сортирующей сети соединен с входом IC₂ компаратора другой ячейки сортирующей сети, то вход Х₂ транспозиционного элемента одной ячейки соединен с выходом Y₂ другой ячейки. Если выходы OC₁, OC₂ выходной ячейки сортирующей сети являются выходами управляющих кодов устройства, то входы X₁, Х₂ транспозиционного элемента этой ячейки являются входами данных. Если входы IC₁, IС₂ входной ячейки сортирующей сети являются входами управляющих кодов устройства, то выходы Y₁, Y₂ транспозиционного элемента этой ячейки являются выходами данных.

Устройство работает следующим образом. На n входов управляющих кодов IC1,IC2,…, ICn, образованных входами компараторов IС₁, IС₂ устройства, подаются входные управляющие коды, представляющие собой перестановку чисел натурального ряда π(1,2,…, n). На n входов данных Х1,Х2,…, Хn, образованных входами транспозиционных элементов Х₁, Х₂ устройства, подаются входные данные (x₁,x₂,…, x_n). Через время задержки τ, на n выходах данных Y1,Y2,…, Yn, образованных выходами транспозиционных элементов устройства, появляются выходные данные, представляющие собой перестановку π(х₁,х₂,…, х_n). Время задержки τ определяется количеством элементов на пути распространения сигналов управления и данных. Если значение кода на входе компаратора IC₁ больше или равно значения кода на входе компаратора IC₂, то значение кода поступает с входа IC₁ на выход OC₁, а значение кода на входе IC₂ поступает на выход ОС₂. Одновременно на управляющем выходе компаратора появляется сигнал, который подается на управляющий вход транспозиционного элемента. При этом перестанавливаемые данные на входе X₁ поступают на выход Y₁; а перестанавливаемые данные на входе Х₂ поступают на выход Y₂.

Если значение кода на входе компаратора IС₁ меньше значения кода на входе компаратора IC₂, то значение кода поступает с входа IC₁ на выход ОС₂, а значение кода на входе IC₂ поступает на выход OC₁. Одновременно на управляющем выходе компаратора появляется сигнал, который подается на управляющий вход транспозиционного элемента. При этом перестанавливаемые данные на входе X₁ поступают на выход Y₂; а перестанавливаемые данные на входе Х₂ поступают на выход Y₁.

Таким образом, перестановка входного вектора данных (х₁,х₂,…, х_n) в соответствии с входными управляющими кодами π(1,2,…, n) выполняется параллельно, что обеспечивает высокую скорость преобразования. Число ячеек устройства зависит от топологии используемой сортирующей сети и для сетей Бетчера составляет O(n·(log₂ n)²). Это число растет практически линейно с ростом n, что делает технически возможным управляемую перестановку больших блоков данных.

Устройство управляемой перестановки информации, хранимой в ЭВМ, с n входами и n выходами управляющих кодов, n входами и n выходами данных, включает в себя сортирующую сеть, каждая ячейка которой состоит из компаратора сортирующей сети, с двумя входами, двумя выходами и выходом управления, который соединен с входом управления транспозиционного элемента ячейки, имеющего два входа и два выхода данных, причем для пар ячеек, компараторы которых соединены между собой в соответствии с топологией сортирующей сети, выполняется условие, если выход компаратора первой ячейки соединен с входом компаратора второй ячейки, то вход транспозиционного элемента первой ячейки соединен с выходом транспозиционного элемента второй ячейки, входы управляющих кодов устройства образованы входами компараторов входных ячеек сортирующей сети, а выходы управляющих кодов устройства образованы выходами компараторов выходных ячеек сортирующей сети, входы данных образованы входами транспозиционных элементов выходных ячеек сортирующей сети, а выходы данных образованы выходами транспозиционных элементов входных ячеек сортирующей сети.