Устройство для приема кода хемминга

 

ОПИСАНИЕ

ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

246353

Союз Советских

Социвлистичвоких

Республик

Зависимое от авт. свидетельства №

Заявлено 28.111.1968 (№ 1228745/18-24) с присоединением заявки №

Приоритет

Опубликовано 11.Ч1.1969. Бюллетень № 11

Дата опубликования описания 28.Х1.1969

Кл. 74b, 8/05

42mа 9/00

МПК G 01s

G 061

УДК 621.398:654.93:621. .396.62:681.325.6 (088.8) Комитет по делам изобретений к открытий при Совете Миикстров

СССР

Автор изобретения

Л. Д. Кислюк

Заявитель

УСТРОЙСТВО ДЛЯ ПРИЕМА КОДА ХЕММИНГА

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

Известно устройство приема кодов,в .целом, содержащее перемножитель, запоминающее устройство, устройство сравнения и устройство управления.

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

Блок управления содержит дополнительный

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

В предложенном устройстве требуется вычислять корреляцию .принимаемого напряжения только с некоторым множеством сигналов, число которых L ((M. Это множество оп25 ределяется по результатам посимвольного приема для кода Хемминга с исправлением одиночной ошибии следующим образом.

Код Хемм инга характеризуется м атр ицей проверок, все (2 — 1) столбцов которой

30 (г — число проверочных символов) представ246353

Таблица 1

Номера столбцов

6 7

9 10

13

14 15

0

Проверочные разряды

Таблица 2

Порядковый номер вектора

3 4

7 8

1 2

5 6

6 7

11 9

8 12

14 15 т;

1 13

10 5

55 ляют собой все возможные r-разрядные двоичные числа, за исключением нулевого числа.

Так, например, для кода Хемминга N (и, к) при n = 15 и к = 11, где и — значность кода

Каждый а-тый столбец матрицы представляет собой проверочное число (синдром) S,, которому соответствует искажение к-ro символа. Так, при искажении первого символа синдром будет S< = 1000. Однако этот же синдром получается при искажении двух, трех и т. д. символов, для которых сумма синдромов по модулю 2 есть 1000. Согласно приведенной матрице будет получен синдром 5ь при искажении 2 и 13 или 2, 3 и 8 или 2, 3, 4 и 7 и т. д. символов. iBcего существует 2 совокупностей, номеров символов, при искажении которых получается один и тот же синдром. Каждую такую совокупность номеров принято характеризовать вектором ошибок, под которым подразумевается и-значная последовательность, у которой на месте искаженных (в,передаваемой кодовой комбинации) символов находятся единицы, а на остальных —,нули, причем число единиц в векторе ошибок называют его весом, Если при посимвольном приеме получается синдром S., то из всех возможных вариантов ошибок наиболее вероятным является искажение и-ro символа, который поэтому при коррекции и изменяется на обратный. Очевидно, что прп искажении двух и более символов изменяется на обратный .не искаженный, а правильный символ, т. е. после коррекции число ошибочных символов увеличивается. При посимвольном приеме из поступивших на вход приемника сигналов извлекается информация только о з наке 1-й посылки aj = 1 или aj = О, тогда как при приеме в целом для вынесения решения о переданном сообщении используется, кроме того, значение модуля интеграла от напряжения сигнала, соответствующего !-й посылке А/. Нетрудно убедиться, что обработка сигнала путем выделения знаков посылки а, определения номера синдрома S. с .последующим отысканием (на основе величины посылки А, ) наиболее вероятного из 2" векторов ошибок V<, соответствующих синдрому S,, и суммирования по модулю 2 1"О с последовательностью знаков посылки Qj по помехоустойчивости полностью эквивалентна приему в целом.

При этом отыскание наиболее вероятного

4 (число, посылок), к — и — r — число информационных символов. При,цикличном варианте эта матрица выглядит следующим образом: вектора ошибок сводится к вычислению суммы А s = ХА! посылок, соответствующих единичным символам вектора V,, и нахож20 дению вектора ошибок Vo с наименьшей Aso.

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

В предложенном устройстве иопользуется тот факт, что при числе искаженных символов, равном или большем минимального расстояния d по Хеммингу между кодовыми комбинациями,,в большинстве случаев (расположения ошибок,по длине кодовой,комбинации) прием в целом приводит к неверному решению. Поэтому следует анализировать не все 2 векторов ошибок, а только те из них, вес которых меньше d. Так как у рассматриваемых кодов Хемминга d = 3, то следует анализировать только вектора ошибок с весом 1 и 2. В дальнейшем для конкретносги описывается устройство для приема,в целом кода Хемминга У (15,11). Для этого кода в каждом столбце таблицы 2, найденной из

40 матрицы проверок, .приведены все возможные совокупности из одного и двух номеров символов, при искажении которых образуется синдром S< — — 1000, Табл. 2 для удобства упорядочена в следующем символе. Совокупностям (векторам ошибок) приовоены порядковые .номера

60 = 1 — 8. Меньший номер т, входящий в определенную пару, записан в верхней строке, а больший номер l — в нижней. Кроме того, величина mg есть возрастающая функция от номера i. Для единообразия в первом столб65 це один и тот же номер записан дважды

246353

99

lб гl

99 98

10 97

Уб

I0

И г9 31 гг

Ю9

12 7

15! бб

76

7,г

78 81 M

У5

Ф УБ

127

//г

77 79 вг

35!

159 /6g

/бl /бЗ

/3

/39r

Ж7 1!

58

97а

Б7 88 5!

Зб

/u9

/u9! т! /51 !!

37 !38

/ЗУ /Зб!

42! гю

/У

rl7

Составитель И. Н. Горелова

Техред Т. П. Курилко Корректор Е Н Миронова

Редактор Семанова

Заказ 2752/8 Тираж 480 Подписное

ЦНИИПИ Комитета по делам изобретений и открытий при Совете Министров СССР

Москва, Центр, пр. Серова, д. 4

Типография, пр. Сапунова, 2

5 бl

//3, 5

ub! а

/3

17

/1 7

1У

16!

У5

15 а5

5 ! !59

87 9У

91

9г

85! г /г/

131

117

//3

1/б

/Л/ !/г!!5