Результат интеллектуальной деятельности: УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ КОЭФФИЦИЕНТОВ БУЛЕВЫХ ПРЕОБРАЗОВАНИЙ НАД ПОЛЕМ ГАЛУА 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 г. и рекомендовано для рассмотрения служебного охраноспособного результата интеллектуальной деятельности авторов.