Устройство для вычисления коэффициентов булевых преобразований над полем галуа gf(2n)



Устройство для вычисления коэффициентов булевых преобразований над полем галуа gf(2n)
Устройство для вычисления коэффициентов булевых преобразований над полем галуа gf(2n)
Устройство для вычисления коэффициентов булевых преобразований над полем галуа gf(2n)
Устройство для вычисления коэффициентов булевых преобразований над полем галуа gf(2n)
Устройство для вычисления коэффициентов булевых преобразований над полем галуа gf(2n)
Устройство для вычисления коэффициентов булевых преобразований над полем галуа gf(2n)
Устройство для вычисления коэффициентов булевых преобразований над полем галуа gf(2n)
Устройство для вычисления коэффициентов булевых преобразований над полем галуа gf(2n)

 


Владельцы патента RU 2475810:

Российская Федерация в лице Министерства промышленности и торговли РФ (RU)

Изобретение относится к вычислительной технике и может быть использовано в системах передачи информации широкополосными фазоманипулированными сигналами в гидроакустических системах на подводных объектах. Техническим результатом является расширение функциональных возможностей устройства при обработке гидроакустических сигналов в виде двоичных дискретных булевых функций над расширением поля Галуа GF(2n). Устройство содержит блок управления, входной и выходной коммутаторы, Log2N ступеней единичного преобразования, где N - число разрядов преобразуемой последовательности, каждая из которых содержит регистр сдвига, умножитель-сумматор над полем Галуа GF(2n), элемент И. 2 ил.

 

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

Известны генераторы ортогональных функций, предназначенные для обработки сигналов: а.с. СССР №92783, МКИ G06S 7/26, G06F 1/00, а.с. СССР №131092, МКИ2 G06S 7/26, а.с. СССР №170298, МКИ3 G06S 7/22, патент США №3742201, кл. G01F 7/38, 26.06.1973 г., G06F 7/00, а.с. СССР №1032451 «Устройство для вычисления симметричных булевых функций», G06F 7/00, а.с. 1084782 «Устройство для вычисления систем булевых функций», «Устройство для вычисления коэффициентов преобразования по Уолшу», G06F 7/38, и др.

Все они предназначены для решения узкого круга задач и не могут быть применены к решению задач, связанных с помехоустойчивым декодированием широкополосных фазоманипулированных сигналов в гидроакустических системах обнаружения, классификации и распознавания объектов. Такой широкий класс задач может быть решен с помощью булевого преобразования над полем Галуа GF (2n) (см., например, В.М.Муттер. Основы помехоустойчивой телепередачи информации, Ленинград, 1990 г.).

Наиболее близким техническим решением к данному изобретению является устройство для вычисления коэффициентов преобразования по Уолшу, а.с. №744555, бюллетень изобретений №24, 1980, содержащее log2N ступеней единичного преобразования, где N - число разрядов преобразуемой последовательности, каждая из ступеней содержит первый регистр сдвига, вход и выход которого соединены со входом сумматора-вычислителя, первый вход которого подключен к первым входам элементов группы совпадений «И», а второй соединен со вторыми входами элементов группы совпадения через второй регистр сдвига, выходы элементов группы совпадения «И» каждой ступени соединены со входами регистра сдвига последующей ступени, и блок управления, выходы которого соединены со вторыми входами элементов группы совпадения «И» всех ступеней единичного преобразования. Недостатком устройства является ограниченное применение его в системах обработки информации, только в базисе функций Уолша, которые не обладают свойствами инвариантности относительно сдвигов по фазе и не могут быть использованы в системах передачи информации с помехоустойчивым кодированием и исправлением ошибок.

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

Цель изобретения достигается тем, что в него введен сумматор-умножитель над полем Галуа GF (2n) (схема которого, например, представлена в книге У.Питерсона «Коды, исправляющие ошибки», М., Мир, 1976, стр.206, рис.7.13), выход которого соединен к первым входом элементов группы совпадения «И», первый вход соединен с выходом входного коммутатора, а второй вход с выходом регистра сдвига, а также выход элемента группы совпадения «И» каждой ступени соединен с первым входом сумматора-умножителя последующей ступени, при этом выход последней ступени соединен с входом выходного коммутатора.

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

Устройство содержит входной коммутатор 1, регистр сдвига 2, сумматор-умножитель 3, группу элементов совпадения «И» 4, блок управления 5 и выходной коммутатор 6.

Регистры сдвига 2 во всех ступенях единичного преобразования задерживают сигнал на одинаковое число тактов, а именно N/2, где N=2n, a n - целое положительное число. Тактовая частота в регистре сдвига 2 первой ступени преобразования равна частоте следования входного сигнала, а тактовая частота регистров сдвига 2 в каждой последующей ступени преобразования в 2 раза больше, чем в предыдущей. Это позволяет получить коэффициенты преобразования от последовательностей, получаемых после каждого нового значения входного сигнала, т.е. составленных из значений входного сигнала от 1-го по N, от 2 по N+1, от 3 по N+2 и т.д.

Рассмотрим работу устройства на примере N=8. В этом случае регистры 2 сдвига в любой ступени преобразования имеют длину 2. С частотой тактовых импульсов в регистре 2 сдвига первой ступени преобразования значения дискретного сигнала последовательно поступают на вход первой ступени преобразования. Сумматор-умножитель 3 производит одновременно умножение значений сигнала с выхода регистра 2 над полем GF (23) и суммирование над полем GF (23). Закон умножения и суммирования представлен на фиг.2 для порождающего полинома X3⊕Х⊕1 над GF (2). Блок элементов группы совпадения «И» работает с частотой в 2 раза больше, чем тактовая частота в регистре сдвига 2, и выдает на входе следующей ступени преобразования последовательность суммы и умножения значений сигнала, поступающих на сумматор-умножитель 3.

Таким образом, во 2 ступень единичного преобразования числа с выхода блока элементов группы совпадения «И» первой ступени преобразования поступают с частотой вдвое больше частоты следования значений входного сигнала. 2 ступень единичного преобразования, как и каждая последующая, работает аналогично первой, но только с частотой, вдвое большей, чем предыдущая. Поэтому на выходе 3 ступени единичного преобразования с частотой в 8 раз больше частоты следования входного сигнала получают коэффициенты булевого преобразования над полем GF (2n) последовательностей, состоящих из значений входного сигнала с 1 по N, с 2 по N+1, с 3 по N+2 и т.д. Блок управления осуществляет управление и синхронизацию устройства.

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

В матричном виде эти преобразования после третьей ступени представлены в виде следующих последовательностей:

где представляет нулевой элемент поля GF (2n), а числа 0, 1, 2, 3, 4, 5, 6 - соответствующее умножение элементов последовательности.

После 2 ступени:

После 1 ступени:

Входной коммутатор 1 перемешивает эти последовательности по следующему закону:

Выходной коммутатор упорядочивает все строки булевого преобразования по следующему закону:

Правило составления входного коммутатора осуществляется с помощью подстановки Галуа по столбцу матрицы Ф, в котором стоит «1»:

Правило составления выходного коммутатора осуществляется с помощью подстановки Галуа по 2 столбцу матрицы Ф:

В основу построений умножителей по ступеням положено утверждение, что 3 есть примитивный элемент по модулю 2n - 1; в данном случае 7. Составляются классы вычетов ступеней 3 по модулю 7: 30=1; 31=3; 32=9 mod 7≡2; 33=27 mod 7≡6; 34=81 mod 7≡4; 35=243 mod 7≡5.

Третья ступень имеет элементарную ячейку, состоящую из умножителей над полем Галуа GF (23):

,

расположенную по главной диагонали матрицы Гуда начиная со второй строки. На первой строке всегда стоит в первом столбце 0.

Вторая ступень матрицы Гуда имеет элементарную ячейку

расположенную по главной диагонали матрицы.

Первая ступень матрицы Гуда имеет элементарную ячейку:

расположенную по главной диагонали и т.д.

Вторым элементом в первом столбце всегда должен стоять 0. Вследствие того, что дискретное булево преобразование осуществляется не с помощью матричного умножения, а с помощью умножения на вектор справа, то в каждом столбце ступеней Гуда должно быть всегда 2 элемента, которыми дополняются столбцы числами 31 и 32.

В настоящее время проведены лабораторные исследования устройства для вычисления булевого преобразования над полем Галуа GF (2n) на компьютере и подготавливается аппаратура передачи информации для натурных подводных исследований на базе преобразований над полем Галуа GF (2n).

Предложенное устройство используется при проведении плановых работ по модернизации одного из разрабатываемых в институте приборов, которое рассмотрено на НТС от 26.02.2009 г. и рекомендовано для рассмотрения служебного охраноспособного результата интеллектуальной деятельности авторов.

Устройство для вычисления коэффициентов булевого преобразования над полем Галуа GF(2n), содержащее Log2N ступеней единичного преобразования, где N=2n - число разрядов преобразуемой последовательности, каждая из ступеней содержит регистр сдвига, элемент группы совпадения «И», выход элементов группы совпадения «И» каждой ступени соединен со входом регистра сдвига последующей ступени, блок управления, выходы которого соединены со вторыми входами элементов группы совпадения «И» всех ступеней единичного преобразования, и входной и выходной коммутаторы, отличающееся тем, что в устройство введен сумматор-умножитель над полем Галуа GF(2n) каждой ступени единичного преобразования, выход которого соединен с первыми входами элементов группы совпадения «И», первый вход соединен с выходом входного коммутатора, а второй вход - с выходом регистра сдвига, а также выход элемента группы совпадения «И» каждой ступени соединен с первым входом сумматора-умножителя последующей ступени, при этом выход последней ступени соединен с входом выходного коммутатора.



 

Похожие патенты:

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

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

Изобретение относится к цифровой вычислительной технике и может быть использовано в процессорных устройствах ЭВМ и в устройствах цифровой автоматики. .

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

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

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

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

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

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

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

Изобретение относится к гидроакустике и может быть использовано в системах целеуказания, самонаведения и телеметрии подводных аппаратов

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

Изобретение относится к вычислительной технике и предназначено для построения однородных вычислительных сред, выполняющих функцию выравнивания порядков двоичных чисел. Техническим результатом является повышение быстродействия за счет параллельно-конвейерного нахождения максимального порядка с помощью анализа разрядных срезов операндов, а затем вычисления разностей максимального порядка и остальных порядков m двоичных чисел. Устройство содержит блок нахождения максимального порядка, состоящий из m-входового элемента ИСКЛЮЧАЮЩЕЕ ИЛИ и m ячеек, каждая из которых включает элементы И, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ, информационные триггеры, и блок вычитания, состоящий из m ячеек, каждая из которых включает элементы И, элементы ИСКЛЮЧАЮЩЕЕ ИЛИ, элемент ИЛИ, элемент НЕ, информационные триггеры. 5 ил.

Изобретение относится к вычислительной технике и может быть использовано при обработке гидроакустических сигналов в системах передачи информации. Технический результат заключается в обеспечении возможности функционирования в реальном масштабе времени. Генератор сигналов содержит log2N ступеней единичного преобразования, где N - число разрядов преобразуемой последовательности, каждая из ступеней содержит регистр сдвига, элементы группы совпадения «И», выходы элементов группы совпадения «И» каждой ступени соединены с входами регистра сдвига последующей ступени, и блок управления, выходы которого соединены со вторыми входами элементов группы совпадения «И» всех ступеней единичного преобразования, в каждой ступени единичного преобразования введен элемент «исключающее ИЛИ», первый вход которого подключен к входу регистра сдвига этой же ступени, а второй вход - к выходу регистра сдвига этой же ступени, при этом выходы элементов «исключающее ИЛИ» соединены с первыми входами элементов группы совпадения «И» той же ступени единичного преобразования. 2 ил.

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

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

Изобретение относится к вычислительной технике и может быть использовано в системах цифровой вычислительной техники как средство предварительной обработки информации. Технический результат заключается в расширении функциональных возможностей, а именно в реализации мажоритарной функции нескольких аргументов - входных двоичных сигналов либо дизъюнкции (конъюнкции) тех же аргументов. Мажоритарный модуль содержит два элемента И (11, 12), два элемента ИЛИ (21, 22) и девять мажоритарных элементов (31, … , 39). За счет указанных элементов и новой схемы их соединения, глубина которой равна четырем, обеспечивается обработка пяти входных двоичных сигналов. В результате достигнуто расширение функциональных возможностей мажоритарного модуля и уменьшение относительного показателя схемной глубины. 1 ил.
Наверх