Устройство формирования обратных перестановок информации, хранимой в эвм
Владельцы патента RU 2446445:
Государственное образовательное учреждение высшего профессионального образования "Саратовский государственный университет им. Н.Г. Чернышевского" (RU)
Устройство относится к области преобразования информации и может быть использовано в вычислительной технике, системах коммуникации и защиты информации от несанкционированного доступа. Техническим результатом является высокоскоростное параллельное формирование перестановок данных, обратных заданным перестановкам данных. Устройство состоит из управляющей сортирующей сети, каждая ячейка которой состоит из компаратора и транспозиционного элемента, компаратор имеет два входа, два выхода и бинарный выход управления, который соединен с входом управления транспозиционного элемента, имеющего два входа и два выхода, причем для пар ячеек, компараторы которых соединены между собой в соответствии с топологией сортирующей сети, выполняется условие, если выход компаратора первой ячейки соединен с входом компаратора второй ячейки, то выход транспозиционного элемента первой ячейки соединен с входом транспозиционного элемента второй ячейки, выходы компараторов выходных ячеек сортирующей сети образуют выходы сортирующей сети, которые соединены с входами сортированных данных, образованными входами входных транспозиционных элементов ячеек сортирующей сети, входы устройства образованы входами компараторов входных ячеек, выходы транспозиционных элементов выходных ячеек являются выходами устройства. 2 ил.
Устройство относится к области преобразования информации и может быть использовано в вычислительной технике, системах коммуникации и защиты информации от несанкционированного доступа.
Под перестановкой информации, хранимой в ЭВМ, понимается упорядоченный набор чисел, образующих n-элементное множество, например, чисел {a 1 ,a 2 ,…,a n }, где a 1 ≤a 2 ≤…≤a n . Часто возникает необходимость быстрого формирования перестановки, обратной заданной.
Известен дешифратор управляемой побитовой транспозиции информации, хранимой в персональной ЭВМ (см. патент РФ №2320000, МПК G06F 7/76). Дешифратор, содержит К уровней узлов дешифрации, каждый уровень дешифрации содержит 2
i
элементов
, регистр управляющих кодов, сдвиговый регистр данных, двойной буферный регистр накопления и хранения форматированных данных, блок управления, генератор тактовых импульсов. Вход выборки дешифратора соединен с первыми входами первого и второго элементов первого уровня. Элемент первого уровня реализует логическую функцию Y
1
=X,
, остальные элементы реализуют логическую функцию
, Y
2
=X
1
×X
2
. Вход Х элемента первого уровня соединен с выходом первого бита регистра управляющих кодов, входы Х
1
остальных элементов i-го уровня соединены с выходом i-го бита регистра управляющих кодов, входы X
2
остальных элементов i-го уровня соединены с выходами элементов i-1 уровня, причем вход двойного буферного регистра накопления и хранения форматированных данных соединен с выходом сдвигового регистра данных, а входы разрешения записи этого регистра соединены с выходами последнего уровня дешифрации. Генератор тактовых импульсов соединен с блоком управления, который своими входами и выходами соединен с буферным регистром накопления и хранения форматированных данных, входным сдвиговым регистром данных, регистром управляющих кодов.
Недостатками данного дешифратора являются невозможность аппаратного формирования обратных перестановок и последовательное преобразование данных, которое происходит за n тактовых импульсов генератора, что при больших значениях n значительно снижает быстродействие.
Известны сортирующие сети Бетчера ("Sorting Networks and Their Applications", К.E. Batcher, Proceedings of 1968 Spring Joint Computer Conference, p.307-314, 1968.). Данные устройства осуществляют быструю сортировку 2 p элементов данных за 1/2р(1+р) шагов, но не обеспечивают формирование обратных перестановок входных данных.
Известна модифицированная сеть Бетчера для сортировки несортированных входных сигналов за log 2 n последовательных проходов. Сеть строится рекурсивно от размера 4 до произвольного размера. Модифицированная сеть Бетчера сортирует n элементов данных за log 2 n последовательных проходов через сеть, где n - число элементов данных для каждого прохода. Сеть имеет задержку на log 2 n компараторах (см. патент US №5319788, МПК G06F 7/36; G06F 7/22).
Однако данная сеть не обеспечивает формирование обратных перестановок входных данных.
Известно устройство для осуществления управляемых перестановок, которое состоит из двух сетей типа «Butterfly» одинакового размера, соединенных одна с другой (back-to-back). Управление осуществляется программно с помощью процессора. С использованием данного устройства можно формировать прямые и обратные перестановки входных данных.
Недостатком данного устройства является программное управление перестановками, которое осуществляется процессором и приводит к замедлению работы системы (см. патент US №6922472, МПК H04L 9/34; H04L 9/34).
Известно устройство управляемой перестановки информации, хранимой в ЭВМ (см. заявка на изобретение RU №2009111245/08 от 30.03.2009). Устройство с n входами и n выходами управляющих кодов, n входами и n выходами данных, включает в себя сортирующую сеть, каждая ячейка которой состоит из компаратора сортирующей сети, с двумя входами, двумя выходами и выходом управления, который соединен с входом управления транспозиционного элемента ячейки, имеющего два входа и два выхода данных, причем, для пар ячеек, компараторы которых соединены между собой в соответствии с топологией сортирующей сети выполняется условие, если выход компаратора первой ячейки соединен с входом компаратора второй ячейки, то вход транспозиционного элемента первой ячейки соединен с выходом транспозиционного элемента второй ячейки, входы управляющих кодов устройства образованы входами компараторов входных ячеек сортирующей сети, а выходы управляющих кодов устройства образованы выходами компараторов выходных ячеек сортирующей сети, входы данных образованы входами транспозиционных элементов выходных ячеек сортирующей сети, а выходы данных образованы выходами транспозиционных элементов входных ячеек сортирующей сети.
Однако данное устройство не обеспечивает формирование обратных перестановок входных данных.
Задачей настоящего решения является ускорение процесса формирования обратных перестановок входных данных, при минимизации элементов устройства.
Техническим результатом является возможность высокоскоростного параллельного формирования перестановок, обратных заданным перестановкам данных в ЭВМ.
Поставленная задача достигается тем, что устройство формирования обратной перестановки информации, хранимой в ЭВМ, с n входами данных и n выходами данных, согласно решению включает в себя сортирующую сеть, каждая ячейка которой состоит из компаратора и транспозиционного элемента, компаратор имеет два входа, два выхода и бинарный выход управления, который соединен с входом управления транспозиционного элемента ячейки, имеющего два входа и два выхода, причем для пар ячеек, компараторы которых соединены между собой в соответствии с топологией сортирующей сети, выполняется условие, если выход компаратора первой ячейки соединен с входом компаратора второй ячейки, то выход транспозиционного элемента первой ячейки соединен с входом транспозиционного элемента второй ячейки, выходы компараторов выходных ячеек сортирующей сети образуют выходы сортирующей сети, которые соединены с входами сортированных данных, образованными входами входных транспозиционных элементов ячеек сортирующей сети, входы устройства образованы входами компараторов входных ячеек сортирующей сети, а выходы устройства образованы выходами транспозиционных элементов выходных ячеек сортирующей сети.
Для быстрого формирования обратной перестановки предлагается использовать структуру сортировочной сети. Если Р - преобразование, осуществляемое сортирующей сетью, a π(a 1 ,a 2 ,…,a n ) некоторая перестановка, то
Р(π(a 1 ,a 2 ,…,a n ))=E;
где Е=(a 1 ,a 2 ,…,a n ) - тождественная перестановка.
Если умножить данное выражение справа на π -1 (a 1 ,a 2 ,…,a n ) и использовать свойство ассоциативности перестановок, получим
Pππ -1 =Eπ -1 ⇒P(a 1 ,a 2 ,…,a n )=π -1 (a 1 ,a 2 ,…,a n ).
Таким образом, для формирования обратной перестановки необходимо применить преобразование Р к отсортированному набору чисел (a 1 ,a 2 ,…,a n ). При этом, если на сортирующую сеть Р наложить сеть с аналогичной динамической топологией, получим устройство, реализующее заданную перестановку π -1 (a 1 ,a 2 ,…,a n ).
Изобретение поясняется чертежами, где на фиг.1 приведена блок-схема устройства, на фиг.2 приведена схема устройства на основе топологии сортирующей сети Бетчера для формирования перестановки, обратной перестановке набора данных из четырех элементов π(a 1 ,a 2 ,a 3 ,a 4 ),
где
1 - устройство формирования обратной перестановки;
2 - ячейки сети;
ICS1, ICS2, …, ICSn - n входов данных устройства;
YS1, YS2, …, YSn - n выходов данных устройства;
OCS1, OCS2, …, OCSn - n выходов сортированных входных данных;
XS1, XS2, …, XSn - n входов сортированных входных данных;
π(a 1 ,a 2 ,…,a n ) - перестановка набора чисел, являющаяся входными данными;
π -1 (a 1 ,a 2 ,…,a n ) - обратная перестановка набора чисел, являющаяся выходными данными;
(a 1 ,a 2 ,…,a n ) - сортированные наборы чисел;
X 1 , Х 2 - первый и второй входы транспозиционных элементов ячейки сети;
Y 1 , Y 2 - первый и второй выходы транспозиционных элементов ячейки сети;
IC 1 , IC 2 - первый и второй входы компараторов ячейки сети;
ОС 1 , OC 2 - первый и второй выходы компараторов ячейки сети;
ICS1, ICS2, ICS3, ICS4 - входы данных устройства;
OCS1, OCS2, OCS3, OCS4 - выходы сортированных входных данных;
XS1, XS2, XS3, XS4 - входы сортированных входных данных;
YS1, YS2, YS3, YS4 - выходы данных устройства.
Предлагаемое устройство включает в себя сортирующую сеть 1, в узлах которой находятся ячейки 2, состоящие из компаратора сортирующей сети и транспозиционного элемента управляемой перестановки данных на входах элемента. Компаратор сортирующей сети имеет управляющий выход, два входа IC 1 , IC 2 и два выхода ОС 1 , OC 2 . Транспозиционный элемент имеет вход управления, входы X 1 , Х 2 и выходы Y 1 , Y 2 . В каждой ячейке управляющий выход компаратора соединен с входом управления транспозиционного элемента.
Соединения выходов OC 1 , ОС 2 и входов IC 1 , IC 2 компараторов, определяются топологией используемой сортирующей сети. Соединения входов данных устройства ICS1, ICS2, …, ICSn с входами компараторов входных ячеек сортирующей сети определяются топологией, используемой сортирующей сети. Соединения выходов сортированных входных данных OCS1, OCS2, …, OCSn с выходами компараторов выходных ячеек сортирующей сети определяются топологией используемой сортирующей сети.
Если выход ОС 1 компаратора выходной ячейки сети соединен с i-м выходом сортированных входных данных OCS1, OCS2, …, OCSn, то выход Y 1 транспозиционного элемента этой ячейки соединен с i-м выходом данных устройства YS1, YS2, …, YSn. Если выход ОС 2 компаратора выходной ячейки сети соединен с i-м выходом сортированных входных данных OCS1, OCS2, …, OCSn, то выход Y 2 транспозиционного элемента этой ячейки соединен с i-м выходом данных устройства YS1, YS2, …, YSn.
Если вход IC 1 компаратора входной ячейки сети соединен i-м входом данных устройства ICS1, ICS2, …, ICSn, то вход данных X 1 транспозиционного элемента этой ячейки соединен i-м входом сортированных входных данных устройства XS1, XS2, …, XSn. Если вход IC 2 компаратора входной ячейки сети соединен с i-м входом данных устройства ICS1, ICS2,..., ICSn, то вход данных X 2 транспозиционного элемента этой ячейки соединен с i-м входом сортированных входных данных устройства XS1, XS2, …, XSn.
Если выход ОС 1 компаратора одной ячейки сети соединен с входом IC 1 компаратора другой ячейки сети, то выход Y 1 транспозиционного элемента одной ячейки соединен с входом Х 1 другой ячейки. Если выход ОС 2 компаратора одной ячейки сети соединен с входом IC 2 компаратора другой ячейки сети, то выход Y 2 транспозиционного элемента одной ячейки соединен с входом Х 2 другой ячейки. Если выход ОС 1 компаратора одной ячейки сети соединен с входом IC 2 компаратора другой ячейки сети, то выход Y 1 транспозиционного элемента одной ячейки соединен с входом Х 2 другой ячейки. Если выход ОС 2 компаратора одной ячейки сети соединен с входом IC 1 компаратора другой ячейки сети, то выход Y 2 транспозиционного элемента одной ячейки соединен с входом X 1 другой ячейки.
Таким образом, транспозиционные элементы ячеек внутри сети соединены между собой так же, как компараторы ячеек сортирующей сети.
Выход сортированных входных данных OCS1 соединен с входом XS1 сортированных входных данных, выход сортированных входных данных OCS2 соединен с входом XS2 сортированных входных данных и т.д. Выход сортированных входных данных OCSn соединен с входом XSn сортированных входных данных. Входы IC 1 , IC 2 компараторов входных ячеек сети образуют n входов данных устройства. Выходы Y 1 , Y 2 транспозиционных элементов выходных ячеек сети образуют n выходов данных устройства.
Устройство работает следующим образом. На n входов ICS1, ICS2, …, ICSn, образованных входами компараторов IC 1 , IC 2 входных ячеек сортирующей сети, подаются входные данные, представляющие собой перестановку чисел π -1 (а 1 ,а 2 ,…,a n ). Через время задержки τ на n выходах YS1, YS2, …, YSn, образованных выходами транспозиционных элементов устройства, появляются выходные данные, представляющие собой перестановку π -1 (a 1 ,a 2 ,…,a n ). При этом на выходах сортированных входных данных появляются сортированные входные данные (a 1 ,a 2 ,…,a n ), где a 1 ≤a 2 ≤…≤a n . Время задержки τ определяется количеством ячеек сети на пути распространения данных. Если число на входе компаратора IC 1 больше или равно числу на входе компаратора IC 2 , то число на входе IC 1 поступает на выход OC 1 , a число на входе IC 2 поступает на выход ОС 2 . Одновременно на управляющем выходе компаратора появляется бинарный сигнал, который подается на управляющий вход транспозиционного элемента. При этом перестанавливаемые данные на входе X 1 поступают на выход Y 1 ; а перестанавливаемые данные на входе Х 2 поступают на выход Y 2 .
Если число на входе компаратора IC 1 меньше числа на входе компаратора IC 2 , то число на входе IC 1 поступает на выход ОС 2 , а число на входе IC 2 поступает на выход OC 1 . Одновременно на управляющем выходе компаратора появляется бинарный сигнал, который подается на управляющий вход транспозиционного элемента. При этом перестанавливаемые данные на входе Х 1 поступают на выход Y 2 ; а перестанавливаемые данные на входе Х 2 поступают на выход Y 1 .
Таким образом, транспозиционный элемент ячейки осуществляет транспозицию данных на своих входах тогда и только тогда, когда компаратор ячейки осуществляет транспозицию данных на своих входах.
Если сортированный набор чисел (а 1 ,а 2 ,…,a n ) известен заранее, его можно сразу подать на входы XS1, XS2, …, XSn для увеличения быстродействия устройства.
Таким образом, формирование перестановки обратной перестановке π(a 1 ,a 2 ,…,a n ) выполняется параллельно, что обеспечивает высокую скорость преобразования. Число ячеек устройства зависит от топологии используемой сортирующей сети и для сетей Бетчера составляет O(n·(log 2 n) 2 ). Это число растет практически линейно с ростом n, что делает технически возможным получение обратных перестановок для больших значений n.
Устройство формирования обратной перестановки информации, хранимой в ЭВМ, с n входами данных и n выходами данных, характеризующееся тем, что включает в себя сортирующую сеть, каждая ячейка которой состоит из компаратора и транспозиционного элемента, компаратор имеет два входа, два выхода и бинарный выход управления, который соединен с входом управления транспозиционного элемента ячейки, имеющего два входа, и два выхода, причем для пар ячеек, компараторы которых соединены между собой в соответствии с топологией сортирующей сети, выполняется условие, если выход компаратора первой ячейки соединен с входом компаратора второй ячейки, то выход транспозиционного элемента первой ячейки соединен с входом транспозиционного элемента второй ячейки, выходы компараторов выходных ячеек сортирующей сети образуют выходы сортирующей сети, которые соединены с входами сортированных данных, образованными входами входных транспозиционных элементов ячеек сортирующей сети, входы устройства образованы входами компараторов входных ячеек сортирующей сети, а выходы устройства образованы выходами транспозиционных элементов выходных ячеек сортирующей сети.
