Декодер кодов рида-соломона

 

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

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

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК (5!)5 Н 03 М 13/02

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

IlO ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ

ПРИ ГКНТ СССР

Р"

1;.

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

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 4665651/24 (22) 24.03.89 (46) 23.11.92. Бюл. ¹ 43 (72) С.Л.портной, А.С.Скороваров, С.Б.Жиронкин, А.Л.Дейч и А,Е.Тузков (56) Вопросы радиоэлектроники. Серия: Техника проводной связи, 1975, № 11, с. 64-69..

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

hL 1640830, кл. Н 03 М 13/02, 1988.

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

¹ 1690202, кл. Н 03 М 13/02, 1988.

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

Цель изобретения — повышение помехозащищенности и информативности декодера.

Функциональная схема декодера при- . ведена на фиг. 1. На фиг. 2 и 3 представлены схемы соответственно блока стековых регистров и блока управления.

Декодер кодов Рида-Соломона (РС) содержит первый — десятый регистры 1-10 сдвига, блок 11 стековых регистров, блок 12 определения индексов максимальной надежности, блок 13 преобразования кодов, первый и второй элементы 14, 15 задержки, первый — третий кольцевые регистры 16-18, компаратор 19. кодер 20 кода РС, первый— пятый коммутаторы 21-25, счетчик 26 числа различий, блок 27 сравнения с единицей, блок 28 сравнения с двойкой, блок 29 управления, первый — третий вентильные элементы 30-32, первую и вторую группы 33, 34 вентильных элементов.. Ы 1777244А1

{54) ДЕКОДЕР КОДОВ РИДА-СОЛОМОНА (57) Изобретение относится к вычислительной технике и технике связи; его использование в многоканальных системах передачи информации позволяет повысить помехозащищенность и информативность декодера.

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

На фиг. 1 обозначены первые и вторые информационные входы 35, 36, адресные входы 37, первый и второй входы 38, 39 констант, информационные и адресные выходы 40, 41. Блок 11 стековых регистров (фиг. 2) содержит первый и второй демультиплексоры

42, 43, дешифратор 44, первую группу 45 регистров сдвига, группу 46 счетчиков импульсов, вторую rpynny 47 регистров сдвига, шифратор 48, первый и второй мультиплексоры 49, 50.

На фиг. 2 обозначены первые — третьи и четвертый входы 51-54, первые — третьи выходы 55-57.

Блок 29 управления (фиг. 3) содержит первый и второй регистры 58, 59 сдвига, компаратор 60, первый — четвертый элементы 61-64 ИЛИ, коммутатор 65, первый и второй счетчики 66. 67 импульсов.

На фиг. 3 обозначены первые и второй входы 68, 69, первый — четвертый выходы

70-73.

На фиг, 1-3 разрядность соединений обозначена косой чертой, перечеркиваю1777244 число информационных символов, каждый из которых имеет разрядность Q и сопровождается символом надежности разрядно- 20

40

50 кодового слова и в регистр надежности при- 55 кятого кодового слова. По величине значещей соответствующую линию, рядом с которой указана величина разрядности.

Блок 12 определения индексов максимальной надежности, блок 13 преобразования кодов (из системы остаточных классов через обобщенную позиционную систему в позиционную систему) и кодер 20 кода PC выполнены тэк же, кэк и в прототипе.

На фиг. 1 ке показан тактовый генератор, тактирующий работу регистров 1-10, 16-18, блоков 11, 13 и кодера 20 аналогично тому, как это делается в прототипе.

На фиг. 1 и 3 показаны соединения в коммутаторах 21-25 и 65 при нулевых сигналах на их управляющих входах.

Декодер предназначен для декодирования (и. k) — кодов PC (где п — длина кода, k— стью М), поступающих из m каналов со стираниями.

Для выбранного кода РС (n, k), строится множество прямых проективной плоскости

PG (2, q), где q + q + 1 « k + д, а д = q + 1.

В зависимости от количества ошибок в принятом кодовом слове декодер осуществляет либо одну попытку декодиоовэния, либо 1+ (k+ 1)/2 попыток, либо q + q+ 1 попыток, что обеспечивает адаптивность декодирования и при обслуживании m каналов одновременно дает среднее время декодирования, равное утроенному времени декодирования с исправлением только стираний, В основе работы декодера лежит следующий алгоритм.

Из m каналов на входы декодера поступают Q-ичные символы кодовых слов и Mичные значения их надежности, при этом на адресные входи декодера поступает номер канала, по которому поступил данный сигнал. Символы кодовых слов, поступающие на вход жестких значений декодера одновременно с их надежностями, поступающими на вход надежности кодовых символов декодера, записываются в стековых регистрах ассоциативно с номером канала. (Стеки жестких значений и надежности для данкоl0 канала заполняются cNHxpoHHO), При заполнении одной пары из 2m стеков происходит перезапись содержимого стеков соответственно в регистр принятого ния надежности отбираются (k + д) наиболее надежных символов прикятого кодового слова, 5

Далее следует процедура N.1: :k символов из отобранных подвергаются преобразованию из системы остаточных классов в обобщенно-позиционную систему и из обобщенно-позиционной системы в позиционную систему. Полученный информационный набор кодируется в позиционную систему. Полученный информационный набор кодируется кодом PC (n, k).

Далее следует сравнение синтезированного кодового слова с принятым из канала в (k + 2) позициях и в (k + д )позициях.

В зависимости от числа различий в указанных позициях осуществляется либо 1+(k

+ 1)/2 попыток декодирования при помощи процедуры N 1, в результате выполнения этой группы попыток получают кодовое слово, обладающее наименьшим числом различий с принятым из канала кодовым словом, с последующим сравнением получившегося кодового слова e(k+ 2) и s(k+ д ) позициях, либо (1+3) попыток декодирования при помощи процедуры М 1, при этом отобранным символам ставятся в соответствие точки проективной геометрии PG (2, р), где q + q

+ 1 K k+ д.. По определению проективной геометрии, через любые две различные точки проходит единственная прямая. Указанное обстоятельство гарантирчет. исправление двух ошибок при переборе(М+д) прямых, так как при этом обязательно два ошибочных символа попадут на одну прямую проективной плоскости.

Таким образом, осуществляется исправление и (k+ д) стираний, одной или двух ошибок.

Декодер работает следующим образом. . Двоичная последовательность, содержащая (k+ д ) элементов. поступает на первый вход 38 констант и записывается в пятый регистр 5, одновременно вторая двоичная последовательность, содержащая (k+

2) элементов, поступает и записывается через второй вход 39 констант в восьмой регистр 8.

На адресные входы 37 поступает номер активного канала. Одновременно жесткие значения символов кодового, слова поступают на первые информационные входы 35 и записываются ассоциативно с номером канала s один из.m регистров сдвига стековых регистров) первой группы 45 жестких значений блока 11. Одновременно на вторые икформационные входы 36 поступают значения надежности кодовых символов и соответственно номеру канала записываются в один из а стековых регистров второй группы 47. Каждая пара стеков, закреплен1777244 ная за определенным каналом, заполняется синхронно.

При заполнении одной пары из 2 m стековых регистров 45, 47 блока 11 происходит одновременная перезапись содержимого блока 11 стековых регистров соответственно в третий и первый регистры 3 и 1 сдвига.

С выходов последнего значения надежности поступают на входы блока 12 определения индексов (k + д ) наиболее надежных символов кодового слова.

Отобранные индексы поступают и записываются во второй регистр 2 сдвига, одновременно двоичная последовательность выделенных позиций кодового слова записывается в девятый регистр 9 сдвига, при этом с управляющих разрядных выходов второго регистра 2 сдвига управляющие сигналы поступают на соответствующие разрядные входы управления перезаписью третьего регистра 3 сдвига, с разрядных информационных Q-ичных выходов которого отобранные символы кодового слова поступают на разрядные информационные входы четвертого регистра 4 сдвига, при этом выполняется следующая процедура N. 1.

На входы управления четвертого и второго регистров 4 и 2 с разрядных выходов пятого (восьмого) регистра 5 (8) сдвига поступает k разрешающих сигналов перезаписи, в соответствии с которыми k символов жестких значений и k значений надежности с последовательных выходов регистров 4 и

2 поступают на входы блока 13 преобразования кодов. Одновременно с последовательных выходов третьего регистра 3 сдвига на информационные входы второго кольцевого регистра 17 поступает принятое кодовое слово, а с разрядных выходов девятого регистра 9 сдвига на входы первого кольцевого регистра 16 поступает двоичная последовательность, содержащая (k + д ) разрешающих сравнение сигналов.

С выходов блока 13 преобразования кодов декодированный информационный набор поступает на входы шестого регистра 6 сдвига, с выходов которого информационный набор поступает на входы кодера 20 кода РС, с выходов которого синтезированное кодовое слово поступает на информационные входы третьего кольцевого регистра

18. С выходов второго и третьего кольцевых регистров 17, 18.сигналы подаются на компаратор 19. с выхода которого информация о посимвольном различии поступает на счетный вход счетчика 26 числа различий, 5

55

22 поступает на входы управления третьего и пятого коммутаторов 23, 25 и второй вход

69 блока 29; При этом происходит выполнение процедуры М Х

Код числа различий поступает с первых входов 68 блока 29 управления в первый регистр 41 и записывается во второй регистр 59, далее происходит сравнение содержимого регистров 58 и 59, При выполнении в компараторе 60 одного из условий сравнения сигнал поступает на первый элемент 61 ИЛИ, с его выхода через коммутатор 65 проходит на вход второго счетчика 67, разряды всех выходов которого подключены к входам четвертого элемента содержимое которого при этом записывается в десятый регистр 10 сдвига, С выхода регистра 10 код числа различий через третий коммутатор 23 поступает либо на входы блока 21 сравнения с единицей, либо на входы блока 22 сравнения с двойкой в зависимости от положения первого и второго коммутаторов 21, 22, в которых проверяются следующие условия: если число различий в k + 2 позициях >1, то сигнал поступает на входы управления третьим и четвертым коммутаторами 23 и 24, При этом . код числа различий с выходов десятого регистра.10 поступает на первые входы 68 блока 29 управления, и происходит циклический сдвиг последовательности в пятом регистре 5 на два разряда и повторение процедуры М 1. При этом каж -. дое порождение кодового слова сопровождается процедурой hh 2.

Код числа различий записывается в первый регистр 58 блока 29 управления и на первом цикле — во второй регистр 59. Далее происходит сравнение содержимого регистров 58 и 59 при помощи компаратора 60

Сигнал на выходе "А< Б" подается на входы перезаписи шестого регистра 6 сдвига и второго регистра 59 блока 29 и, кроме того., на первый элемент 61 ИЛИ, с выхода которого через коммутатор 65 он проходит на вход первого счетчика 66. Все разряды выходов последнего подключены к входам второго элемента 62 ИЛИ, кроме выхода старшего разряда, соответствующего (k +

1)/2-му циклу, который подключен к перво му входу третьего элемента 63 ИЛИ. При этом сигнал с выхода второго элемента 62

ИЛИ управляет сдвигом в восьмом регистре

8. а сигнал с выхода третьего элемента 63

ИЛИ управляет третьим коммутатором 15.

Если же в блоке 21 число различий в k+

2 позициях 1, то происходит сравнение в (k + д ) позициях в блоке 22. Если число различий > 2, то управляющий сигнал с блока

1777244

64 ИЛИ. кроме выхода старшего разряда, подключенного к второму входу третьего элемента 63 ИЛИ. При этом сигнал с выхода четвертого элемент 64 ИЛИ управляет сдвигом пятого регистра 5, а сигнал с выхода третьего элемента 63 ИЛИ управляет третьим коммутатором 23. Каждому сдвигу в пятом регистре 5 соответствует процедура

hk 1.

Если в блоке 22 число различий в k+

+ д позициях 2, то управляющий сигнал поступает на вход разрешения перезаписи в седьмой регистр 7 сдвига, при этом декодированная информация поступает на информационные выходы 40 одновременно с номером канала, по которому она была принята на адресных выходах 4!. Далее происходит сброс всех регистров, кроме пятого и восьмого, и перезапись содержимого следующей пары заполненных стеков иэ блока 11.

Если в результате выполнения процеду. ры % 3 число различий не станет 2, произойдет отказ от декодирования.

Для кода Рида-Соломона с параметрами (31, 15) энергетический выигрыш кодирования в канале с ортогональными сигналами при Ре- 10 составляет около 3 дБ.

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

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

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

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

40 первого — третьего кольцевых регистров, выходы счетчика числа различий подключе. ны к входам десятого регистра сдвига, выходы которого соединены с информационными входами третьего ком45 мутатора, первые выходы которого подключены к информационным входам первого и второго коммутаторов, вторые выходы третьего коммутатора соединены с первыми входами блока управления. второй выход

50 которого подключен к входу третьего вентильного элемента, выходы первого — третьего вемтильмых элементов соединены с управляющими входами третьего и пятого коммутаторов и вторым входом блока управ55 лемия. выходы второго коммутатора подключены к входам блока сравнения с двойкой, выход "Больше" которого соединен с входом второго вентильного элемента, выход Больше" блока сравнения с единицей подключен к входу первого вентильного

1777244

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

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

20 -разряд, .соединены с входами соответст25

35

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

З.-,Цекодер по и. 1, отличающийся тем, что блок управления содержит первый и второй регистры сдвига, компаратор, первый — четвертый элементы ИЛИ, коммутатор, первый и второй счетчики импульсов, венно второго и четвертого элементов ИЛИ, выходы старших разрядов счетчиков импульсов подключены к входам третьего элемента ИЛИ, информационные входы первого регистра сдвига являются первыми входами блока, параллельные выходы первого регистра сдвига соединены с входами второго регистра сдвига, последовательные выходы первого и второго регистров сдвига подключены соответственно к первым и вторым входам компаратора, выход "Меньше" которого соединен с первым входом первого элемента ИЛИ, входом разрешения сдвига первого регистра сдвига и является первым выходом блока, выходы "Больше" и

"Равно" компаратора подключены к второму и третьему входам первого элемента

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

1777244

1777244

Фиг. 7

Составитель О.Ревинский

Техред М.Моргентал Корректор М.ПетРова

Редактор

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

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

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

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