n
УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ КОЭФФИЦИЕНТОВ БУЛЕВЫХ ПРЕОБРАЗОВАНИЙ НАД ПОЛЕМ ГАЛУА GF(2)
n
APPARATUS FOR CALCULATING GALOIS FIELD GF(2) BOOLEAN TRANSFORMATION COEFFICIENTS

Изобретение относится к вычислительной технике и предназначено для использования в системах передачи информации широкополосными фазоманипулированными сигналами в гидроакустических системах на подводных объектах.
2
3
Известны генераторы ортогональных функций, предназначенные для обработки сигналов: а.с. СССР №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, и др.
n
Все они предназначены для решения узкого круга задач и не могут быть применены к решению задач, связанных с помехоустойчивым декодированием широкополосных фазоманипулированных сигналов в гидроакустических системах обнаружения, классификации и распознавания объектов. Такой широкий класс задач может быть решен с помощью булевого преобразования над полем Галуа GF (2) (см., например, В.М.Муттер. Основы помехоустойчивой телепередачи информации, Ленинград, 1990 г.).
2
Наиболее близким техническим решением к данному изобретению является устройство для вычисления коэффициентов преобразования по Уолшу, а.с. №744555, бюллетень изобретений №24, 1980, содержащее logN ступеней единичного преобразования, где N - число разрядов преобразуемой последовательности, каждая из ступеней содержит первый регистр сдвига, вход и выход которого соединены со входом сумматора-вычислителя, первый вход которого подключен к первым входам элементов группы совпадений «И», а второй соединен со вторыми входами элементов группы совпадения через второй регистр сдвига, выходы элементов группы совпадения «И» каждой ступени соединены со входами регистра сдвига последующей ступени, и блок управления, выходы которого соединены со вторыми входами элементов группы совпадения «И» всех ступеней единичного преобразования. Недостатком устройства является ограниченное применение его в системах обработки информации, только в базисе функций Уолша, которые не обладают свойствами инвариантности относительно сдвигов по фазе и не могут быть использованы в системах передачи информации с помехоустойчивым кодированием и исправлением ошибок.
Цель изобретения - расширение области применения, заключающееся как в возможности функционирования устройства в режиме реального времени, так и режиме помехоустойчивого декодирования с исправлением ошибок в системах обработки широкополосных фазоманипулированных сигналов.
n
Цель изобретения достигается тем, что в него введен сумматор-умножитель над полем Галуа GF (2) (схема которого, например, представлена в книге У.Питерсона «Коды, исправляющие ошибки», М., Мир, 1976, стр.206, рис.7.13), выход которого соединен к первым входом элементов группы совпадения «И», первый вход соединен с выходом входного коммутатора, а второй вход с выходом регистра сдвига, а также выход элемента группы совпадения «И» каждой ступени соединен с первым входом сумматора-умножителя последующей ступени, при этом выход последней ступени соединен с входом выходного коммутатора.
На фиг.1 представлена схема устройства, на фиг.2 - последовательность вычисления.
Устройство содержит входной коммутатор 1, регистр сдвига 2, сумматор-умножитель 3, группу элементов совпадения «И» 4, блок управления 5 и выходной коммутатор 6.
n
Регистры сдвига 2 во всех ступенях единичного преобразования задерживают сигнал на одинаковое число тактов, а именно N/2, где N=2, a n - целое положительное число. Тактовая частота в регистре сдвига 2 первой ступени преобразования равна частоте следования входного сигнала, а тактовая частота регистров сдвига 2 в каждой последующей ступени преобразования в 2 раза больше, чем в предыдущей. Это позволяет получить коэффициенты преобразования от последовательностей, получаемых после каждого нового значения входного сигнала, т.е. составленных из значений входного сигнала от 1-го по N, от 2 по N+1, от 3 по N+2 и т.д.
3
3
3
Рассмотрим работу устройства на примере N=8. В этом случае регистры 2 сдвига в любой ступени преобразования имеют длину 2. С частотой тактовых импульсов в регистре 2 сдвига первой ступени преобразования значения дискретного сигнала последовательно поступают на вход первой ступени преобразования. Сумматор-умножитель 3 производит одновременно умножение значений сигнала с выхода регистра 2 над полем GF (2) и суммирование над полем GF (2). Закон умножения и суммирования представлен на фиг.2 для порождающего полинома X⊕Х⊕1 над GF (2). Блок элементов группы совпадения «И» работает с частотой в 2 раза больше, чем тактовая частота в регистре сдвига 2, и выдает на входе следующей ступени преобразования последовательность суммы и умножения значений сигнала, поступающих на сумматор-умножитель 3.
n
Таким образом, во 2 ступень единичного преобразования числа с выхода блока элементов группы совпадения «И» первой ступени преобразования поступают с частотой вдвое больше частоты следования значений входного сигнала. 2 ступень единичного преобразования, как и каждая последующая, работает аналогично первой, но только с частотой, вдвое большей, чем предыдущая. Поэтому на выходе 3 ступени единичного преобразования с частотой в 8 раз больше частоты следования входного сигнала получают коэффициенты булевого преобразования над полем GF (2) последовательностей, состоящих из значений входного сигнала с 1 по N, с 2 по N+1, с 3 по N+2 и т.д. Блок управления осуществляет управление и синхронизацию устройства.
n
Предлагаемое устройство к каждому новому значению входного сигнала вычисляет коэффициент булевого преобразования над GF (2) от последовательностей, состоящих из N предыдущих значений сигнала, что позволяет использовать его в системах реального времени, а единообразие в системах единичного преобразования дает возможность использовать идентичные ступени единичного преобразования.
В матричном виде эти преобразования после третьей ступени представлены в виде следующих последовательностей:
n
где представляет нулевой элемент поля GF (2), а числа 0, 1, 2, 3, 4, 5, 6 - соответствующее умножение элементов последовательности.
После 2 ступени:
После 1 ступени:
Входной коммутатор 1 перемешивает эти последовательности по следующему закону:
Выходной коммутатор упорядочивает все строки булевого преобразования по следующему закону:
Правило составления входного коммутатора осуществляется с помощью подстановки Галуа по столбцу матрицы Ф, в котором стоит «1»:
Правило составления выходного коммутатора осуществляется с помощью подстановки Галуа по 2 столбцу матрицы Ф:
n
0
1
2
3
4
5
В основу построений умножителей по ступеням положено утверждение, что 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.
3
Третья ступень имеет элементарную ячейку, состоящую из умножителей над полем Галуа GF (2):
,
расположенную по главной диагонали матрицы Гуда начиная со второй строки. На первой строке всегда стоит в первом столбце 0.
Вторая ступень матрицы Гуда имеет элементарную ячейку
расположенную по главной диагонали матрицы.
Первая ступень матрицы Гуда имеет элементарную ячейку:
расположенную по главной диагонали и т.д.
1
2
Вторым элементом в первом столбце всегда должен стоять 0. Вследствие того, что дискретное булево преобразование осуществляется не с помощью матричного умножения, а с помощью умножения на вектор справа, то в каждом столбце ступеней Гуда должно быть всегда 2 элемента, которыми дополняются столбцы числами 3 и 3.
n
n
В настоящее время проведены лабораторные исследования устройства для вычисления булевого преобразования над полем Галуа GF (2) на компьютере и подготавливается аппаратура передачи информации для натурных подводных исследований на базе преобразований над полем Галуа GF (2).
Предложенное устройство используется при проведении плановых работ по модернизации одного из разрабатываемых в институте приборов, которое рассмотрено на НТС от 26.02.2009 г. и рекомендовано для рассмотрения служебного охраноспособного результата интеллектуальной деятельности авторов.