ПАРАЛЛЕЛЬНЫЙ ДЕШИФРАТОР УПРАВЛЯЕМОЙ ТРАНСПОЗИЦИИ ИНФОРМАЦИИ, ХРАНИМОЙ В ПЕРСОНАЛЬНОЙ ЭВМ Российский патент 2010 года по МПК G06F7/00 

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

Известно устройство линейного дешифратора (см. патент РФ № 2032937, МПК G06F 11/00), содержащее К уровней узлов дешифрации (К - разрядность информационного входа дешифратора). В устройство введено К элементов НЕ, а каждый узел дешифрации выполнен в виде мажоритарного элемента. Каждый уровень дешифрации содержит 2i мажоритарных элементов . Вход выборки дешифратора соединен с первыми входами первого и второго мажоритарных элементов первого уровня. Выход каждого мажоритарного элемента i-го уровня соединен с первыми входами пары мажоритарных элементов (i+1)-го уровня, выходы мажоритарных элементов k-го уровня являются выходами дешифратора, информационные входы которого соединены с входами элементов НЕ и соответственно с вторыми входами четных мажоритарных элементов уровней с первого по k-й. Вторые входы нечетных мажоритарных элементов которых соединены соответственно с выходами элементов НЕ. Третьи входы нечетных мажоритарных элементов всех уровней соединены с первым управляющим входом дешифратора, второй управляющий вход которого соединен с третьими входами четных мажоритарных элементов всех уровней.

Однако это устройство функционально не решает задачу управляемой транспозиции данных.

Известен коммутатор на базе коммутационной матрицы, основанной на комбинационной схеме, аналогичной предлагаемой (http://www.unix.com.ua/lsok/glava_7.htm). Коммутационная матрица состоит из уровней двоичных переключателей, которые соединяют свой вход с одним из двух выходов в зависимости от значения бита тэга. Переключатели первого уровня управляются первым битом тэга, второго - вторым и т.д.

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

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

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

Задачей настоящего решения является ускорение процесса форматирующего преобразования произвольной транспозиции информации за счет одновременной (параллельной) перестановки входного вектора данных (α₁, α₂, …, α_N), при минимизации логических вентилей матрицы дешифратора.

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

Поставленная задача достигается тем, что дешифратор управляемой транспозиции информации, хранимой в персональной ЭВМ, содержащий K уровней узлов дешифрации, регистр управляющих кодов, содержащий биты управляющих кодов, согласно решению содержит N=2^K входов данных и выполнен с возможностью перестановки вектора входных данных длиной N параллельно. Для этого узлы дешифрации выполнены на одинаковых логических элементах, имеющих первый и второй входы данных X₁, X₂, первый и второй выходы данных Y₁, Y₂ и вход управляющего кода COD, причем каждый логический элемент электрически соединен входом COD с соответствующим битовым выходом регистра управляющих кодов, каждый логический элемент i-го уровня дешифрации с номером j электрически соединен первым выходом данных Y₁ с первым входом данных X₁ элемента i+1 уровня дешифрации с номером j, а вторым выходом данных Y₂ со вторым входом данных Х₂ элемента i+1 уровня дешифрации с номером входы данных элементов первого уровня дешифрации являются входами данных дешифратора, выходы данных элементов К-го уровня дешифрации являются выходами данных дешифратора, где i - номер уровня дешифрации, j - номер уровня логического элемента, INT - функция выделения целой части числа.

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

1) регистр управляющих кодов;

2) матрица дешифратора;

3) X₁, Х₂ - первый и второй входы данных узла дешифрации;

4) Y₁, Y₂ - первый и второй выходы данных узла дешифрации;

5) COD - вход управляющего кода.

Предлагаемый параллельный дешифратор управляемой транспозиции информации состоит из регистра управляющих кодов 1 и матрицы дешифратора 2 (фиг.1), выполняющей функцию перестановки вектора данных (α₁, α₂, …, α_N). Матрица дешифратора выполнена на одинаковых логических элементах, имеющих два входа данных X₁, X₂, два выхода данных Y₁, Y₂ и вход управляющего кода COD (см. фиг.2). Каждый логический элемент осуществляет транспозицию данных Y₁=X₂, Y₂=X₁ при высоком логическом уровне на входе COD или передает данные без изменения Y₁=X₁, Y₂=X₂ при низком логическом уровне на входе COD. Входы кодов матрицы дешифратора соединены с выходами регистра управляющих кодов. Число логических элементов матрицы дешифратора где - уровней дешифрации.

Работа дешифратора поясняется графом, представленным на фиг.3, выполненным для N=16, К=4. Логические элементы фиг.2 располагаются в вершинах графа. На входы данных элементов первого уровня дешифрации подаются элементы входного вектора данных (α₁, α₂, …, α_N). Каждый элемент i-го уровня дешифрации с номером j электрически соединен первым выходом данных с первым входом данных элемента i+1 уровня дешифрации с номером j, а вторым выходом данных со вторым входом данных элемента i+1 уровня дешифрации с номером Выходы данных элементов К-го уровня дешифрации являются выходами данных дешифратора.

Устройство работает следующим образом. Перед началом преобразования в регистр управляющих кодов записывается N/2·log₂N бит управляющих кодов, каждый их которых управляет соответствующим логическим элементом узла дешифратора. На входы дешифратора подаются элементы входного вектора данных. Через время задержки преобразования на выходах дешифратора появляется перестановка входного вектора данных. Время задержки выполнения перестановки Т определяется временем задержки на логическом элементе узла матрицы дешифратора τ и числом уровней дешифрации K:T=K·τ.

Таким образом, перестановка входного вектора данных длиной N в соответствии с управляющими кодами в регистре управляющих кодов выполняется параллельно, что обеспечивает высокую скорость преобразования. Число логических элементов дешифратора N/2·log₂N растет практически линейно с ростом N, что делает технически возможным перестановку больших блоков данных. Число возможных перестановок, осуществляемых данным дешифратором, 2^N/2·log ₂  ^N < N!, т.к. данный дешифратор не реализует полное множество возможных перестановок вектора входных данных.

Изобретение относится к области кодирования информации и может быть использовано в вычислительной технике и в системах защиты информации от несанкционированного доступа. Техническим результатом является возможность высокоскоростного параллельного преобразования форматов блоков данных методом транспозиции с использованием управляющих кодов. Дешифратор управляемой транспозиции информации, хранимой в персональной ЭВМ, содержит К уровней узлов дешифрации, регистр управляющих кодов, содержащий биты управляющих кодов. Узлы дешифрации выполнены на одинаковых логических элементах, имеющих первый и второй входы данных Х₁, Х₂, первый и второй выходы данных Y₁, Y₂ и вход управляющего кода COD. 3 ил.

Дешифратор управляемой транспозиции информации, хранимой в персональной ЭВМ, содержащий узлы дешифрации, которые образуют К уровней, регистр управляющих кодов, содержащий биты управляющих кодов, отличающийся тем, что он содержит N=2^K входов данных и выполнен с возможностью перестановки вектора входных данных длиной N параллельно, при этом узлы дешифрации выполнены на одинаковых логических элементах, имеющих первый и второй входы данных Х₁, Х₂, первый и второй выходы данных Y₁, Y₂ и вход управляющего кода COD и осуществляющих транспозицию данных на входах данных Y₁=X₂, Y₂=X₁ при высоком логическом уровне на входе COD или передающих данные на входах данных без изменения Y₁=X₁, Y₂=X₂ при низком логическом уровне на входе COD, причем каждый логический элемент электрически соединен входом COD с соответствующим битовым выходом регистра управляющих кодов, каждый логический элемент i-го уровня дешифрации с номером j электрически соединен первым выходом данных Y₁ с первым входом данных X₁ элемента i+1 уровня дешифрации с номером j, а вторым выходом данных Y₂ со вторым входом данных Х₂ элемента i+1 уровня дешифрации с номером , входы данных элементов первого уровня дешифрации являются входами данных дешифратора, выходы данных элементов К-го уровня дешифрации являются выходами данных дешифратора, где i - номер уровня дешифрации, j - номер уровня логического элемента, INT - функция выделения целой части числа.