Устройство для декодирования кода нордстрома-робинсона в дискретном канале

 

Изобретение относится к вычислительной технике и может быть исполь-. зовано при разработке аппаратуры передачи Дискретной информации„ Цель изобретения - повышение корректирующей способности и быстродействия устройства за счет сложения входного кодового слова с образующими смежных классов и декодирования полученных кодовых слов усеченными декодерами кода Рида- Маллера. Устройство содержит 7 блоков сложения с образующими смежного класса (1), 8 усеченных декодероэ кода Рида-Маллера (2), блок ключей

СОЮЗ СОВЕТСНИХ

РЕСПУБЛИИ (f91 (1В

А1 (Я)5 " o3 М 13/00

ГОСУДАРСТВЕННЫЙ КОМИТЕТ

00 ИЭОБРЕТЕНИЯМ И 07КЯр ГИЯМ

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 4768677/24

{22) 12. 12.89 (46). 23.05.92. Бюл. 19 (71) Пермский сельскохозяйственный институт им. акад, Д,Н, Прянишникова (7?) А.Е. Ашихмин, В.А. Зиновьев,.

С.Н. Лицын и С,Л. Портйой (53) 681.325(088.8) (56) Кодирование и передача дискретных сообщений по каналам связи.-М,:

Наука, 1976, с. 74-75.

Авторское свидетельство СССР

Г 11 08618, кл. Н 03 М 13/02, 1980 ° (54) УСТРОЙСТВО ДЛЯ ДЕКОДИРОВАНИЯ КОДА НОРДСТРОМА - РОБИНСОНА В ДИСКРЕТНОМ КАНАЛЕ

2 (57) Изобретение относится к вычислительной технике и может быть исполь-.

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

Маллера, Устройство содержит 7 блоков сложения с образующими смежного класса (1), 8 усеченных декодеров кода Рида-Маллера (2) блок ключей (3), блок сравнения (4) и выходной буферный регистр (5). 1-2-4-3"5, 2"3;

4-5 1 и ф-лы 3 ил, 3 173

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

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

Уолша и схемы выбора максимального элемента.

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

1 шибок, четырех- и пятиразрядный счетчики, два блока управления, тактовыи генератор, два пороговых элемента, кодер кода Рида-Соломона, кодер кода

Нордстрома-Робинсона.

Недостатками известного устройства является низкое быстродействие и бо1 ее низкая по сравнению с максимумом правдоподобия корректирующая способность.

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

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

6008 с соответствующими информационными входами блока ключей, выходы которого соединены.с первыми входами выходного буферного регистра, вторые входы ко- торого подключены к выходам блока сравнения, шестые выходы всех усеченных декодеров кода Рида-Маллера сое-" динены с входами блока сравнения,;вь ю ходы выходного буферного регистра яв- ляются выходами устройства.

Кроме того, в устройстве усеченный декодер кода Рида-Маллера содержит блоки сложения-вычитания, блоки сум15 пирования модулей блоки сравнения, блоки ключей и блок определения знака числа, входы первого блока сложениявычитания являются входами декодера, первые выходы первого .- третьего бло2О ков сложения-вычитания соединены с первыми информационными входами одноименных блоков ключей и входами адно" именных блоков .суммирования модулей, выход каждого блока суммирования мо"

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

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

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

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

На фиг. 1 изображена структурная схема устройства для декодирования

55 кода Нордстрома-Робинсона.. на фиг,2 i усеченный декодер кода Рида-Маллера; на фиг. 3 - граф-схема, Устройство для декодирования кода

Нордстрама-Робинсона содержит блоки 1 делах кодового расстояния (6=8), т,е, исправляющее ошибки кратности три включительно, Декодер кодов Нордстрома-Робинсона будет тогда исправлять все двухкратные ошибки; а также те трехкратные и четырехкратные ошибки, которые исправляются при декодировании по максимуму правдоподобия. Поскольку результаты работы декодирующего устройства, работающего по максимуму правдоподобия, и устройства усеченного декодирования (декодирование в пределах кодового расстояния) для векторов с ошибками кратности 0,1,2,3 одни и те же и поскольку вектора с пятью, шестью кратными ошибками будут в каком-то смежном классе являться векторами с ошибками кратности, меньшей пяти, и так как в столбце таблицы стандартного расположения должно находиться ровно определенное число векторов, то число правильно декодируемых векторов с ошибками кратности четыре при работе декодера кода РидаМаллера по максимуму правдоподобия и работе усеченного декодера будет одинаковым, Следовательно, устройство для декодирования кода Нордстрома-Робинсона, использующее усеченный деко дер кода Рида-Маллера, будет устрой ством декодирования по .максимуму правдоподобия (данное утверждение проверено на ЭВМ путем декодирования двумя способами всех двоичных последовательностей длины 16).

Пример, Пусть в линию связи посла н вектор длины 1 б v = (1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1).

Ка приемной стороне принимается векторw= (-1, 1, 1, 1, 1, -1, 1, 1, 1, -1, 1, 1,- 1, 1, 1, 1) с ошибками на первой, шестой и десятой позициях.

Элементы принятого вектора попарно складываем и вычитаем, затем находим сумму з модуЛей элементов, -полученных сложением, и сравниваем ее с восемью, Если в 8, то на дальнейшее декоди:рование пропускаем элементы, полученные сложением, если s В О, то на дальнейшее декодирование пропусканием элементы, полученные вычитанием, при этом на каждом шаге получаем очередной информационный символ (1 если s 3, 1 если s .8), Ila последнем шаге определяем знак элемента (полученного сложением, если в > 8), полученного вычитанием, если в(8) - это дает пятый ин45

5 173"008 6 сложения с образующим смежного клас- са, усеченные декодеры 2 кода Рида Маллера, блок 3 ключей, блок 4 сравнения, . выходной буферный регистр .

Блок I сложения с образующим смежного класса представляет собой набор шести инверторов, инвертирующих элементы исходного вектора в соответствии с образующим данного смежного класса„

Блок 3 ключей представляет собой набор ключей, которые на выход блока пропускают пять информационных символов с усеченного декодера кода

Рида-Маллера, имеющего максимальную сумму на выходе.

Блок 4 сравнения находит усеченный декодер кода Рида-Maллера,,давший максимальную сумму, и кодирует номер этого декодера кода Рида -Маллера тремя 20 двоичными символами.

Регистр 5 представляет собой шестнадцатиразрядный буферный регистр, Усеченный декодер кода Рида-Маллера (фиг, 2) представляет собой декодер кода Рида-Маллера, декодирующий в пределах кодового расстояния, содержащий блоки 6 сложения-вычитания, блоки

7 суммирования модулей, блоки 8 сравнения (с восемью), блоки 9 ключей, блок 10 определения знака числа, 30

Блок сложения и вычитания для j-го этапа (1=1...,,4) содержит 24 сумматоров и 2ч 3 вычитателей, Блок сложения модулей i --го этапа представляет собой 2 -входовой сум- 35

"матор.

Блок сравнения с восемью представляет собой набор пороговых логических схем, срабатывающих при достижении порога (порог равен восьми), 40

Блоки ключей выполнены на базе логи чес ких схем И, WIN, Н Е и служат для пропускания на следующий этап соответствующей группы символов, Блок определения знака числа пропускает на выход знаковый бит числа, Алгоритм работы заключается в следующем. Известно, что радиус покрытия кода Нордстрома-Робинсона равен четы". рем, тогда как радиус покрытия кода 50 Рида-Маллера длины 16 равен шести, поэтому нет необходимости применять устройство декодирования кодов РидаМаллера, работающее по максимуму правдоподобия и исправляющее ошибки 55 кратности шесть включительно. Достаточно построить устройство, декодирующее код Рида-Маллера длины 16 в npe-.! в+ ra(+ ° ° +Iа з+ a q+ a q

° ° + а + а о+ ° +а 1 в =(а,* az) +(a>+ а, в = а, + а + а + a„j в = a<+ а + ° °,+ae + в„- ja,+ а +„,+а„(, 7 173600 формационный символ. Поясним это с помощью граф-схемы (фиг. 3) .

Докажем, что устройство будет исправлять все ошибки кратности 1,2,3. где e„ «+1 " символы, пришедшие иэ канала, Легко видеть, что искажение 15

1 "ro символа влечет уменьшение любой суммы на 2 (если ни один символ не был искажен, то все суммы равны шест" надцати), искажение символов влечет уменьшение любой суммы, т,е. если искажено не более 1рех символов, то любая сумма будет больше восьми и декодирование будет правильным. Таким образом, видно, что усеченный декодер гарантированно исправляет любые три 25 ошибки, При этом число сумматоров уменьшается в одном декодере кода Рида-Иаллера с 64 до 41, а во всем декодере кода Нордстрома-Робинсона с 512 до 312. В декодере по максимуму прав- 30 доподобия необходимо найти максимальный элемент из 16 элементов, для этого требуется провести 15 операций сравнения в декодере кода Рида-Иаллера и 120 операций сравнения в декодере кода Нордстрома-Робинсона, в усечен35 ном декодере кода Рида-Иаллера требуется четыре операции сравнения с константой и 32 операции сравнения сконстантой в декодере кода Нордстрома-Ро- 40 бинсона. Можно оценить уменьшение an" паратурных затрат в 1,5 раза, Устройство работает следующим образом.

Кодовый вектор длины 16 приходит из линии связи и поступает на входы блоков 1 сложения с образующими смежных классов, с выходов которых результаты поступают на входы усечен" . ных декодеров 2 кода Рида-Иаллера (по- 5О скольку один из образующих смежных классов состоит из одних нулей, то в этом случае можно декодируемый вектор ,сразу подать на усеченный декодер 21 кода Рида-Иаллера). На выходах усе55 ченных декодеров 2 кода Рида-Иаллера имеем по пять информационных симво" лов и максимальный коэффициент корреляции ° В блоке 4 сравнения подкодов

8 Я

Так как код Рида-Иаллера - линейный, то беэ потери общности можно полагать, что передавался вектор, состоящий иэ одних единиц. Тогда на шагах 1...,,4 будем иметь соответственно; находим больший из коэффициентов корреляции, что дает три информационных символа, которые поступают на вторые входы регистра 5 записи декодированного слова, С.усеченного декодера 2, давшего наибольший коэффициент корреляции, пропускаем пять информационных символов на первые входы регистра 5 записи декодированного слова.

Таким образом, получаем устройство для декодирования кода НордстромаРобинсона, содержащее меньшее количество логических элементов по сравнению с известным устройством, работающее как комбинационная схема в отличие от известного устройства и обес печивающее исправление всех возможных ошибок, Формула изобретения

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

Рида"Иаллера, первые - пятые выходы всех усеченных декодеров кода РидаИаллера соединены с .соответствующими информационными входами блока ключей, выходы которого соединены с первыми

9 173600 входами выходного буферного регистра, вторые входы которого подключены к выходам блока сравнения, шестые выходы всех усеченных декодеров кода РидаИаллера-, соединены с входами блока сравнения, выходы выходного буферного регистра являются выходами устройства, 2. Устройство по и. 1, о т л ич.а ю щ е е с я тем, что усеченный декодер. кода Рида-Иаллера содержит ,блоки сложения-вычитания, блоки суммирования модулей, блоки сравнения, блоки ключей и блок определения знака числа, входы первого блока сложения-вычитания являются входами декодера, первые выходы первого-третьего блоков сложения-вычитания соединены с первыми информационными входами одноименных блоков ключей и входами одноименных блоков суммирования модулей, выход каждого блока суммирования модулей подключен к входу одноименного блока сравнения, вторые выходы первого " третьего блоков сложения-вычитания соединены с вторыми

8 10 информационными входами одноименных блоков ключей, выходы которых подключены к входам соответственно второгочетвертого блоков сложения-вычитания, первый выход четвертого блока сложения-вычитания соединен с входом четвертого блока сравнения и первым информационным входом четвертого блока ключей, второй выход четвертого блока сложения-вычитания подключен к второму информационному входу четвертого блока ключей, прямые выходы первогочетвертого блоков сравнения соединены с первыми управляющими входами одноименных блоков ключей и являются соответственно первым - четвертым вы" ходами декодера, инверсные выходы первого — четвертого блоков сравнения подключены к вторым управляющим входам одноименных блоков ключей, выход блока определения знака числа является . пятым выходом декодера, выход четвертого блока ключей соединен с входом блока определения знака числа и является шестыч выходом декодера, 1736оо8 .1 . f

ÄI

М!

1736008

2 4 Ю

2 б 2

2 ф -2 и„= О. u>=0

S=JO>8 и--О

2

0

= 10r8

2 О

S = 1От8

A=0

Редактор Н. Тупица

Заказ 1824 Тираж . Подписное

ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР

113035, Иосква, Ж-35 ° Раушская наб., д. 4/5

Производственно-издательский комбинат "Патент", г. Ужгород, ул. Гагарина, 101

-1

1

1

-7

1

-1

1

1

Составитель А, Ашихмин

Техред M. Дидык Корректор С. йекмар