Устройство для декодирования кода Нордстрома-Робинсона в дискретном канале Советский патент 1992 года по МПК H03M13/00 

з 17

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

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

Устройство содержит восемь блоков декодирования биортогонального кода, основанных на быстром преобразовании Уолша и схемы выбора максимального элемента„

Наиболее близким техническим решением является устройство декодировани кода Нордстрома-Робинсонасодержащее

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

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

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

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

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

30

35

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

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

45 блоков сравнения подключены к вторым управляющим входам одноименных блоков ключей, выход блока определения знака числа является пятым выходом декодера выход четвертого блока ключей соеди50 нен с входом блока определения знака числа и является шестым выходом блока«

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

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

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

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

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

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

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

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

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

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

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

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

делах кодового расстояния () , т.е. исправляющее ошибки кратности три включительно. Декодер кодов Нордстро- ма-Робинсона будет тогда исправлять все двухкратные ошибки, а также те трехкратные и четырехкратные ошибки, которые исправляются при декодировании по максимуму правдоподобия Пос

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

с образующим данного смежного класса 10 кольку результаты работы декодирующего

Блок 3 ключей представляет собой устройства, работающего по максимуму набор ключей, которые на выход бло- правдоподобия, и устройства усеченно- ка пропускают пять информационных сим- го декодирования (декодирование в пре- волов с усеченного декодера кода делах кодового расстояния) для векто- Рида-Наллера, имеющего максимальную ров с ошибками кратности 0,1,2,3 одни сумму нэ выходе,,- --

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

Регистр 5 представляет собой шестнадцатиразрядный буферный регистр.

Усеченный декодер кода Рида-Маллера (фиг, 2) представляет собой деко- 25 ТЬ1Ре ПРИ работе декодера кода Рида- дер кода Рида-Маллера, декодирующий в Маллера по максимуму правдоподобия и пределах кодового расстояния, содержащий блоки 6 сложения-вычитания, блоки 7 суммирования модулей, блоки 8 сравнения (с восемью), блоки 9 ключей, блок 10 определения знака числа,

Блок сложения и вычитания для j-ro этапа (,,./,) содержит . сумматоров и вычитателей.

Блок сложения модулей -го этапа

представляет собой 2 J -входовой сум-35 ностей длины 16) матор. Пример Пусть в линию связи

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

Блоки ключей выполнены на базе логических схем И, ИЛИ, НЕ и служат для пропускания на следующий этап соответствующей группы символов,

Блок определения знака числа пропускает на выход знаковый бит числа.

и те же и поскольку вектора с пятью, шестью кратными ошибками будут в каком-то смежном классе являться векторами с ошибками кратности, меньшей 2Q пяти, и так как в столбце таблицы стандартного расположения должно находиться ровно определенное число векторов, то число правильно декодируемых векторов с ошибками кратности чеработе усеченного декодера будет одинаковым. Следовательно, устройство для декодирования кода Нордстрома-Робинсона, использующее усеченный декодер кода Рида-Маллера, будет устройством декодирования по максимуму правдоподобия (данное утверждение проверено на ЭВМ путем декодирования двумя способами всех двоичных последователь30

1 , 1, 1, 1 , 1, 1, 1, 1, 1 , 1 , 1, 1,

1, D.

На приемной стороне принимается вектор w (-1, 1, 1, 1, 1, -1, 1, 1, 1, -1, 1, 1 ,- 1, 1, 1, 1) с ошибками на первой, шестой и десятой позициях Элементы принятого вектора попарно 45 складываем и вычитаем, затем находим сумму s модул ей элементов, полученных

Алгоритм работы заключается в следующем. Известно, что радиус покрытия кода Нордстрома-Робинсона равен четы-, рем, тогда как радиус покрытия кода Рида-Маллера длины 16 равен шести, поэтому нет необходимости применять устройство декодирования кодов Рида- Маллера, работающее по максимуму правдоподобия и исправляющее ошибки кратности шесть включительно,, Достаточно построить устройство, декодирующее код Рида-Маллера длины 16 в преустройства, работающего по максимуму правдоподобия, и устройства усеченно- го декодирования (декодирование в пре- делах кодового расстояния) для векто- ров с ошибками кратности 0,1,2,3 одни - --

5 ТЬ1Ре ПРИ работе декодера кода Рида- Маллера по максимуму правдоподобия и

и те же и поскольку вектора с пятью, шестью кратными ошибками будут в каком-то смежном классе являться векторами с ошибками кратности, меньшей Q пяти, и так как в столбце таблицы стандартного расположения должно находиться ровно определенное число векторов, то число правильно декодируемых векторов с ошибками кратности чеТЬ1Ре ПРИ работе декодера кода Рида- Маллера по максимуму правдоподобия и

ностей длины 16) Пример Пусть в линию связи

работе усеченного декодера будет одинаковым. Следовательно, устройство для декодирования кода Нордстрома-Робинсона, использующее усеченный декодер кода Рида-Маллера, будет устройством декодирования по максимуму правдоподобия (данное утверждение проверено на ЭВМ путем декодирования двумя способами всех двоичных последователь

послан вектор длины 16 v (1, 1,

1 , 1, 1, 1 , 1, 1, 1, 1, 1 , 1 , 1, 1,

1, D.

На приемной стороне принимается вектор w (-1, 1, 1, 1, 1, -1, 1, 1, 1, -1, 1, 1 ,- 1, 1, 1, 1) с ошибками на первой, шестой и десятой позициях Элементы принятого вектора попарно складываем и вычитаем, затем находим сумму s модул ей элементов, полученных

сложение м, и сравниваем ее с восемью, Сели г, 8, то на дальнейшее декодирование пропускаем элементы, полученные сложением, если s&C, то на дальнейшее декодирование пропусканием элементы, полученные вычитанием, при этом на каждом шаге получаем очередной информационный символ (1 если s 8, 1

если ). На последнем шаге определяем знак элемента,(полученного сложением, если ), полученного вычитанием, если ) - это дает пятый ин71736008В

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

что передавался вектор, состоящий из

Докажем, что устройство будет ис- -s s одних единиц. Тогда на шагах 1,,..,4 правлять все ошибки кратности 1,2,3 будем иметь соответственно;

в|-|а,+ %| |а,+ а4|+ 0.. аЦ ,-«- аг+ а4 | +.. „+ а,3 + а,4 + а ,5 s |a,+ а2+..„+ав|+.. а1о +.. ,+а,6) ,+ аг+,0.+а,б|,

где &i +1 - символы, пришедшие из канала. Легко видеть, что искажение 1-го символа влечет уменьшение любой суммы на 2 (если ни один символ не был искажен, то все суммы равны шестнадцати), искажение символов влечет уменьшение любой суммы, тсе. если искажено не более трех символов, то любая сумма будет больше восьми и декодирование будет правильным. Таким образом, видно, что ус еченный декодер гарантированно исправляет любые три ошибки. При этом число сумматоров уменьшается в одном декодере кода Рида-Маллера с 6Ь до 1, а во всем декодере кода Нордстрома-Робинсона с 512 до 312. В декодере по максимуму правдоподобия необходимо найти максимальный элемент из 16 элементов, для этого требуется провести 15 операций сравнения в декодере кода Рида-Иаллер и 120 операций сравнения в декодере кода Нордстрома-Робинсона, в усеченном декодере кода Рида-Маллера требуется четыре операции сравнения с константой и 32 операции сравнения с константой в декодере кода Нордстрома-Робинсона „ Можно оценить уменьшение аппаратурных затрат в 1,5 раза.

Устройство работает следующим обра зом.

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

5

5

0

5

0

5

0

5

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

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

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

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

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

0

5

0

5

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

w i irf

I Т

.

J

91

№1Г71

« и

Н

0|

J

У

J

)

W5

1

И

фш.З