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

Формула изобретения

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

Описание изобретения к патенту

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

В основу построений умножителей по ступеням положено утверждение, что 3 есть примитивный элемент по модулю 2ⁿ - 1; в данном случае 7. Составляются классы вычетов ступеней 3 по модулю 7: 3⁰=1; 3¹=3; 3 ²=9 mod 7 2; 3³=27 mod 7 6; 3⁴=81 mod 7 4; 3⁵=243 mod 7 5.

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

,

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

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

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

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

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

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

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

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