Декодер кодов Рида-Соломона Советский патент 1992 года по МПК H03M13/02 

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

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

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

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

На фиг. 1 обозначены первые и вторые информационные входы 35, 36, адресные входы 37, первый и второй входы 38, 39 констант, информационные и адресные выходы 40,41.

Блок 11 стековых регистров (фиг. 2) содержит первый и второй демультиплексоры 42, 43, дешифратор 44, первую группу 45 регистров сдвига, группу 46 счетчиков импульсов, вторую группу 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 разрядность соединений обозначена косой чертой, перечеркиваюу

Ј

Я ю

Ј

щей соответствующую линию, рядом с которой указана величина разрядности.

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

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

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

Декодер предназначен для декодирования (n, k) - кодов PC (где п - длина кода, k - число информационных символов, каждый из которых имеет разрядность Q и сопровождается символом надежности разрядно- стью М), поступающих из m каналов со стираниями.

Для выбранного кода PC (n, k), строится множество прямых проективной плоскости PG (2, q), где q2 + q + 1 k+ 5, а (5 q + 1.

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

В основе работы декодера лежит следующий алгоритм.

Из m каналов на входы декодера поступают Q-ичные символы кодовых слов и М- ичные значения их надежности, при этом на адресные входы декодера поступает номер канала, по которому поступил данный сигнал. Символы кодовых слов, поступающие на вход жестких значений декодера одновременно с их надежностями, поступающи- ми на вход надежности кодовых символов декодера, записываются в стековых регистрах ассоциативно, с номером канала. (Стеки жестких значений и надежности для данного канала заполняются синхронно).

При заполнении одной пары из 2тп стеков происходит перезапись содержимого стеков соответственно в регистр принятого кодового слова и в регистр надежности при- пятого кодового слова. По величине значения надежности отбираются (k + б) наиболее надежных символов принятого кодового слова.

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

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

В зависимости от числа различий в указанных позициях осуществляется либо 1 +(k + 1)/2 попыток декодирования при помощи процедуры № 1, в результате выполнения этой группы попыток получают кодовое слово, обладающее наименьшим числом различий с принятым из канала кодовым словом, с последующим сравнением получившегося кодового слова в (k + 2) и в (k + д ) позициях, либо (k +Ј) попыток декодирования при помощи процедуры № 1, при этом отобранным символам ставятся в соответствие точки проективной геометрии PG (2, q), где q2 + q + 1 i k + д. По определению проективной геометрии, через любые две различные точки проходит единственная прямая. Указанное обстоятельство гарантирует исправление двух ошибок при переборе (k+б прямых, так как при этом обязательно два ошибочных символа попадут на одну прямую проективной плоскости.

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

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

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

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

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

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

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

содержимое которого при этом записывается в десятый регистр 10 сдвига.

С выхода регистра 10 код числа различий через третий коммутатор 23 поступает

либо на входы блока 21 сравнения с единицей, либо на входы блока 22 сравнения с двойкой в зависимости от положения первого и второго коммутаторов 21, 22, в которых проверяются следующие условия: если число различий в k + 2 позициях 1, то сигнал поступает на входы управления третьим и четвертым коммутаторами 23 и 24. При этом код числа различий с выходов десятого регистра- 10 поступает на первые входы 68

блока 29 управления, и происходит циклический сдвиг последовательности в пятом ре- гистре 5 на два разряда и повторение процедуры № 1. При этом каж - дое порождение кодового слова сопровож-.

дается процедурой № 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, то управляющий сигнал с блока

22 поступает на входы управления третьего и пятого коммутаторов 23, 25 и второй вход 69 блока 29. При этом происходит выполнение процедуры № 3.

Код числа различий поступает с первых

входов 68 блока 29 управления в первый регистр 41 и записывается во второй регистр 59, далее происходит сравнение содержимого регистров 58 и 59. При выполнении в компараторе 60 одного из условий сравнения сигнал поступает на первый элемент 61 ИЛИ, с его выхода через коммутатор 65 проходит на вход второго счетчика 67, разряды всех выходов которого подключены к входам четвертого элемента

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

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

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

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

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

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

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

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

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

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

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

0 которого подключен к входу третьего вентильного элемента, выходы первого - третьего вентильных элементов соединены с управляющими входами третьего и пятого коммутаторов и вторым входом блока управ5 ления, выходы второго коммутатора подключены к входам блока сравнения с двойкой, выход Больше которого соединен с входом второго вентильного элемента, выход Больше блока сравнения с единицей подключен к входу первого вентильного

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

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

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

3.-Декодер по п. 1,отличающийся

тем, что блок управления содержит первый и второй регистры сдвига, компаратор, первый - четвертый элементы ИЛИ, коммутатор, первый и второй счетчики импульсов,

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

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

подключены соответственно к первым и вто: рым входам компаратора, выход Меньше которого соединен с первым входом первого элемента ИЛИ, входом разрешения сдвига первого регистра сдвига и является

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

$

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