ЯЧЕЙКА ОДНОРОДНОЙ СРЕДЫ С ПРОГРАММИРУЕМОЙ СТРУКТУРОЙ Российский патент 1999 года по МПК G06F7/00 

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

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

Известна ячейка однородной среды, содержащая элементы И, ИЛИ, 2-2И-2-ИЛИ, НЕ, сумматор по модулю два, триггер [1]. К причинам, предшествующим достижению указанного ниже технического результата при использовании известного устройства, относится то, что известное устройство не имеет регистра кода настройки, усложнен процесс программирования ячейки и отсутствует законченное устройство, синтезированное на основе среды, состоящей из однотипных ячеек.

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

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

Предлагаемое изобретение позволяет осуществлять параллельный ввод-вывод информации из среды. Технический результат выражается в увеличении скорости обмена информации. Сущность изобретения в том, что предлагается ячейка в виде устройства, содержащего триггер 8, первый и второй элементы 2-2И-2ИЛИ (1 и 11), сумматор по модулю два (7), пять элементов И ( 3, 4, 5, 6 и 9), первый и второй элементы ИЛИ (10 и 12) и инвертор (2), особенность предлагаемой ячейки в том, что введены (см. фиг. 1) три элемента И (16, 17 и 18), элемент ИЛИ (13), два инвертора (14 и 15) и регистр кода настройки, в первый и второй разряды которого по входам настройки 1 и 2, предназначенные для записи кода операции, в третий, по входу 3, предназначенный для записи кода выбора значения коэффициента при члене полинома, в соответствие которому поставлена ячейка в однородной среде, в которой программно формируется структура преобразователя информации, выполняющего операции умножения или деления (в зависимости от кода операции) по правилам двоичного поля Галуа GF (2^m) или кольца многочленов, над входными полиномами, элементами указанных алгебраических множеств, в четвертый разряд регистра кода настройки, по входу 4, предназначенный для записи кода определения используемости ячейки, т.е. он может быть использован для "обхода" ячейки при ее неисправности, в пятый разряд регистра кода настройки, по входу 5 предназначенный для записи кода определения тактируемости данной ячейки, в шестой, по входу 6, предназначенный для записи кода выбора выходной ячейки набранного в однородной среде преобразователя, в седьмой, по входу 7, предназначенный для записи кода типа вывода из среды (параллельный или последовательный).

Вход A (19) регистра кода настройки служит для выбора адреса программируемой ячейки, вход Y (20) - предназначен для управления записью кода настройки.

Первый и третий входы первого элемента 2-2И-2ИЛИ соединены с первым и вторым выходами регистра кода настройки соответственно, принимающим сигналы кода операции, четвертый вход элемента 2-2И-2ИЛИ представлен информационным входом ячейки 10, выход первого элемента соединен с первым входом первого элемента И, второй вход которого соединен с третьим выходом регистра кода настройки, (выбор коэффициента при члене полинома, соответствующего степени переменной, выступающей в качестве сомножителя или делителя), выход первого элемента И соединен с первым входом первого сумматора по модулю 2, второй вход соединен с выходом второго элемента И, выход первого сумматора по модулю 2 соединен с информационным входом триггера, тактовый вход которого соединен с выходом четвертого элемента И, второй вход которого представлен тактовым входом ячейки 9, а первый вход соединен с пятым выходом регистра кода настройки, выход сумматора по модулю два соединен также с первым входом четвертого элемента И, второй вход которого соединен с выходом второго разряда регистра кода настройки, на который поступает код операции умножения, вход четвертого элемента И соединен с четвертым входом второго элемента 2-2И-2ИЛИ, второй вход которого соединен с выходом триггера, первый вход соединен с выходом второго элемента НЕ (14), третий вход так же, как и вход второго элемента НЕ, соединен с шестым выходом регистра кода настройки, запись в который производится по входу настройки 6, вход настройки служит для выбора выходной ячейки однородной среды, вторые входы второго (4) и третьего (5) элементов И соединены с информационным входом ячейки, обеспечивающим прямую связь между ячейками среды, первый вход второго элемента И через первый элемент НЕ, как и напрямую, первый вход третьего элемента И соединен с четвертым выходом регистра кода настройки, запись в который производится по входу настройки 4, выход третьего элемента И соединен со вторым входом первого элемента ИЛИ (10), первый вход которого соединен с выходом триггера, а выход представлен информационным выходом ячейки, седьмой выход регистра кода настройки соединен через третий элемент НЕ (15) с первым входом седьмого элемента И (17) и напрямую со вторым входом восьмого элемента И (18), первый вход которого соединен с выходом второго элемента 2-2И-2ИЛИ, выход входом восьмого элемента И представлен параллельным выходом ячейки, второй вход седьмого элемента И соединен с выходом третьего элемента ИЛИ, второй вход которого представлен информационным входом ячейки, предназначенным для "внутреннего" переноса информации в однородной среде с выходной ячейки в структуре преобразователя на общий выход среды, первый вход третьего элемента ИЛИ соединен с выходом второго элемента 2-2И-2ИЛИ, выход седьмого элемента И представлен последовательным выходом ячейки, выход третьего элемента НЕ (15) соединен со вторым входом шестого элемента И (16), первый вход которого соединен с выходом второго элемента 2-2И-2ИЛИ, а выход представлен вторым входом второго элемента ИЛИ (12), первый вход которого представлен входом информационной обратной связи между ячейкам среды, выход его представлен выходом ячейки, используемый для связи с ячейками предшествующими данной в однородной среде, соединен со вторым входом первого элемента 2-2И-2ИЛИ, обеспечивая обратную связь в самой ячейке.

На фиг. 1 приведена функциональная схема ячейки однородной полиномиальной среды.

Ячейка однородной среды с программируемой структурой состоит из двух элементов 2-2И-2ИЛИ 1 и 11, триггера 8, сумматора по модулю два 7, трех элементов НЕ 2, 14 и 15, восьми элементов И 3, 4, 5, 6, 9, 16, 17 и 18, трех элементов ИЛИ 10, 12 и 13 и регистра кода настройки 10, имеет четыре информационных входа 8, 9, 10 и 11, семь входов управления 1, 2, 3, 4, 5, 6 и 7, четырех информационных входа 12, 13, 14 и 15.

Описание работы ячейки однородной среды с программируемой структурой по фиг. 1.

Сигналы, записанные по управляющим входам 1 и 2, обеспечивают выбор операции, в выполнении которой в составе преобразователя "набранного" в среде участвует данная ячейка. Логическая единица на входе 1 замыкает цепь обратной связи внутри самой ячейки и с ячейками, находящимися в среде после данной, через вход ячейки 13, что необходимо при выполнении операции деления в полях Галуа и при "пересылке" информации с одной области среды в другую. Логическая единица на входе 2 обеспечивает информационную связь со входом однородной среды при выполнении операции умножения. Логическая единица на входе настройки 3 обеспечивает участие переменной на входах 10 или 13 в суммировании по модулю 2 в первом сумматоре с переменной на информационном входе 11, что имеет место при единичном значении коэффициента при условной переменной, в соответствие которой в полиноме-множителе или делителе (элементах поля) поставлена ячейка, кроме того этот сигнал настройки может быть использован для записи информации в данную ячейку по входу 13 (из ячейки, расположенной в однородной среде после нее). Логическая единица на входе настройки 4 обеспечивает прохождение информации со входа 11 на выход 16 (что может быть использовано для "обхода" ячейки в среде при ее неисправности). Логическая единица на входе настройки 5 обеспечивает тактирование записи и считывания информации в триггере ячейки (определяет ячейки, участвующие в преобразовании информации, вводимой на вход среды). Логическая единица на входе настройки 6 означает, что данная ячейка выбрана в среде в качестве последней в структуре преобразователя. Логическая единица, записанная по входу 7, определяет тип вывода информации как параллельный, при уровне логического нуля вывод последовательный. Информационный вход ячейки 10 используется для организации информационного переноса в ячейке. Логическая единица на входе 18 при уровне логической единицы на входе 17, означает что программируется данная ячейка, обеспечивает запись информации по управляющим входам 1, 2, 3, 4, 5, 6 и 7.

На фиг. 2 приведены соединения ячеек в однородной полиномиальной среде.

Описание схемы соединения ячеек в однородной программно-управляемой среде и ее работы по фиг. 2.

В однородной среде программно, с помощью сигналов настройки, формируется структура преобразователя информации. Определяются ячейки, участвующие в процессе преобразования, определяются входная и выходная ячейки преобразователя. На фиг. 2 приведен пример построения однородной полиномиальной среды на предлагаемых ячейках. Среда содержит n ячеек, соединенных последовательно, информационные входы 8 всех ячеек соединены с общим входом среды, используемым при необходимости ввода одинаковой информации в ячейки, выбранные сигналами настройки на входах 3, и при выполнении в среде операции умножения полиномов. Выход 13 каждой предшествующей ячейки соединен со входом 9 последующей и выведен на шину данных, выход 14 предыдущей ячейки соединен со входом 10 последующей и используется для "переноса" информации с выхода преобразователя на выход 14 последней n-й ячейки среды, так как выходом преобразователя может быть любая ячейка среды, выход 12 каждой последующей ячейки соединен со входом 11 предыдущей и служит для организации обратной связи с выхода K-й ячейки преобразователя на входы всех предшествующих ячеек среды. Входы 16 всех ячеек среды соединены с общей линией тактовых сигналов ТИ. Входы настройки ячеек однородной полиномиальной среды соединены со входами регистров кода настойки этих ячеек, информация в которых определяет выполняемые ячейкой и средой функции (входы 1 и 2), структуру преобразователя (вход 3), выходную ячейку среды (вход 6), тактируемые в среде ячейки (вход 5), участвующие в преобразователе исправные ячейки (вход 4), тип вывода информации параллельный или последовательный (входы 7). Входы 17 всех ячеек образуют шину адреса, а входы 18 шину управления записью, с помощью которых управляющая информация записывается в регистр кода настройки каждой ячейки. Входы 15 образуют выходную шину данных, которая позволяет параллельное считывание информации со всех ячеек одновременно.

Для умножения двоичных полиномов в алгебраическом кольце многочленов или поле Галуа GF (2^m) один из них "набирается" программно в однородной среде, а другой по тактам и поразрядно, вводится по входу 9 первой ячейки среды. Число тактов определяется разрядностью вводимого полинома. Результат умножения снимается с выхода 14 последней ячейки среды. Если число ячеек среды, участвующих в выполнении операции, меньше, чем число ячеек в среде, то сигнал проходит с выхода схемы умножения последней из участвующих ячеек - через входы 10 и выводы 14 промежуточных ячеек, или снимается параллельно по входам 15 ячеек схемы умножения. Для получения произведения в среду следует подавать после ввода сомножителя столько тактов, какого число ячеек памяти (триггеров) в схеме умножения. При этом сигнал со входа среды подается на входы 8 всех ячеек и при наличии сигнала разрешения на входе настройки 2 любой ячейки он "попадает" в ячейку. Сигнал "разрешения" на входе 3 имеет место при равенстве единице коэффициента переменной соответствующей степени полинома сомножителя, "набранного" в среде.

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

Операция деления полиномов в поле Галуа GF (2^m) выполняется путем программного "набора" полинома-делителя в однородной среде, с поразрядным вводом по входу 9 входной ячейки среды по тактовым сигналам в среду при инициированном входе 1 всех ячеек, соответствующих ненулевым составляющим полинома-делимого. Операция деления выполняется за число тактов, равных разрядности двоичной последовательности, соответствующей делимому. Операция деления множества входных последовательностей на данный с анализом остатка от деления может быть использована при декодировании циклических кодов с обнаружением ошибок.

Пересылка содержимого ячейки "i" в ячейку "k" происходит следующим образом:
- при k > i путем организации "обхода" всех промежуточных ячеек среды управляющими сигналами по входу настройки 4;
- при i > k путем "назначения" ячейки "i"
в качестве выходной ячейки в среде сигналом по входу настройки этой ячейки 6 и установкой управляющих сигналов по входам 1 и 3 принимающей ячейки.

Установка триггеров выбранных ячеек в состояние "1" осуществляется установкой уровня логической "1" по входам их настройки 2 и 3 и подачей символа "1" на вход среды.

Преимущество изобретения в том, что увеличивается скорость обмена информация.

Библиографические данные:
1. Авторское свидетельство СССР N 1573456, кл. G 06 F 7/00, 1990 г.

2. Патент N 2029354, кл. G 06 F 7/00, 1995 г.

3. Патент N 2059284, кл. G 06 F 7/00, 1996 г.

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

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