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

(зй)5 Х 03 М 13/02 ГОСУДАРСТВЕННЫЙ КОМИТЕТПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ ОПИСАНИЕ ИЗОБРЕТЕНИЯ Г О К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ(54) ДЕКОДЕР КОДОВ РИДА-СОЛОМОНА 57) Изобретение относится к вычислительной технике. Использование его в системах передачи информации по каналам с О-ичными сигналами позволяет повысить помехо 50, 1690202 А 1 защищенность декодера, содержащего регистр 1 принятого кодового слова, регистр 2 выбранных кодовых символов, блок 3 преобразования кодов, регистр 4 надежностей кодовых символов, блок 5 определения индексов максимальных надежностей, регистр 6 выбранных индексов и регистр 10 декодированного слова. Благодаря введению регистра 7 выбранных надежностей, блока 8 поразрядного сравнения, ключа 9, регистра 11 копии, кодера 12 кода Рида-Соломона п, К), компаратора 13, счетчика 14 числа различий, блока 15 управления, кольцевого сдвигового регистра 16, блока 17 сравнения с единицей и элементов 18 и 19 развязки в декодере обеспечивается исправление одной или двух ошибок и истираний. 1 з,п. ф-лы, 3 ил,Лзсбретение относится к ьычислительай технике и мажет быть использовано в сист 6 мах Передачи информации па каналам с 0-ичными си налами, а также в качестве внешнего декодера касэдных кодов.Цел иэсбретрия - повышение поме хозащищеннасти декОдеса.На фиГ. 1 приведена функциональная схема декодера; иа фиг. 2 и 3 - выполнение соответственна блока управления и блока и 060 бразования кодов.Декодер кодов Рида-Ссг 10 мона (РС) содержит регистр 1 прииятаГО КОДОВОГО слОм, регистр 2 Выбранных адовых символов блок 3 преобразования кодов, регистр 4 надежности кодовых символов, блок 5 определения индексов максимальных надежностей, регистр 6 выбранных индексов, регистр 7 вы бранных надежност;й, блок 8 поразрядного сравнения, ключ 9, регистр 10 декадированного слова, регистр 11 кс пии, кодер 12 кода РС, компаратор 13., счетчик 14 числа различий, блок 15 управления, кольцевой сдвиговый регистр 16, бло 17 сравнения с единицей, первый и второй элементы 18 и 19 развязки, На фиг, 1 обозначены первые и вторые информационные входи 20 и 21 и входы 22 констат, Цег:и тактироваиия и начальной установки не показаны, Раэряднссть соединений обозначена возле косой честы, пересекаюшей ссогветствующ)пс ли.нию (фиг, 1),В основе работы декодера лежит следующий вновь разрабстань ый алгоритм быст рого декодирования кода РС (и, 1), где и - длина кодового славь, ; - числа информационных символов, Из канага связи иа входы 20 и 21 декодера пас) упа к)т О-ичные се Валы КОДОВОГО слава и М-иные значения надежна+ ги приня.:ЧГим вол-,в кацо:г-, слава. По В 8 личине надежности Отбираются ,+ д и)свае на 1 Рчы) имвсло приия тОГО кодсВОГО слова, Этим символам ставят- ГЯ Э СООТВЕТСТВИЕ та"КИ ПР 06 КГИЕгОй плоскости РО 2,с, 1 где с + 0+1(+ а., д =- 0 + 1 следующИМ Образам, "апись пря" мой РО 12,цпредставляет собой последовательность "О" и "1", состоящая иэ ; + + ) элементов паин, м илевымл,.,еи;.ам сООтВетстВует инфармациси:ый иаб" р. ЦИКЛ И 1 дСчи СДВля Т, Г 1 ащ Лг В тдЛ Ь ность х + д раэ атнпсительиа списка стабраниых символов ксДовага слова, ПОЛ 1 суаеМ ПРОЕКТ:1 Р 13 га ПГОСиаСг, ПЯ РЫМИ которсЙ являются Вс, эазможиы 8 калсвые слова, получаемые п)и кзждО 1 сдвиге лсслеДОват 8 льнасти пу тем преабразава.ий иэ системы Остатйчных класссГ В обобщенно-ГОзиционную с;стему и из абабщенио 5 10 15 20 25 3 О 35 45 50 55 позиционной системы в Г.озиционную систему и псследующеГО кодирования кодом РС (и, 1:) аазличных информационных наборов, поступасщих с Выхода блока 3 преобразования кодов.По определению проективной геометрии через гпобые две различные точки проходит единственная г)ямая. Укаэанное обстоятельство гараити сует исправление двух ошибок при переборе М+ д прямых и исправление истираний. Перебор д+1 прямой позволяет исправить одну ошибку.Таким образом осуществляется полный или часнй перебор, в заисиоси От состояния канала связи, максимум за к+ + д циклических сдвигов последовательности, позволяющий исправить одну или две ошибки и истирачий.Блок 15 управ)ения (фиг, 2) содержит формирсватель 23 импульса, первый элемент 24 задержки, регистр 25 числа различий, регистр 26 копии, компаратор 27, первьй сумматор 28, перекгючатель 29, счетчик 30 циклов, дешифратор 31, второй сумматор 32, Второй элемент 33 задержки и элемент 34 развязки, На фиг, 2 обсзначеды первые, второй и третий входы 35-37 и первый-четв;тый выходы 38-41.БПОк " пр 80 браэавания кОдОВ служит для преобразования из системы остаточных классов в а" абщеиную позиционную систему, а из нсе - в позиционную систему. Блок 3 содержит (фиг. 3) блок 41 оперативной памяти, тактовый генератор 42, первый и второй арифметика-логические блоки (АЛ Б) 43 и 44 и блок 45 микракоманднага управления, выполненный иа ПЗУ. Песвый АЛБ 43 содержит группу регистров 4 С, сумматоры 47 в голе 6 Щ) и делитель 48 В поле ОГД), Г)тарой АЛБ 44 содержит групп г регистров 49, умножитель 50 В поле ОР,0) и сумматор 51 в поле ОГД).Блок 5 определения индексов максимальных иадежнсс-ей мажет быть выполнен на ПЗУ, Кодер 12 кода РС выполняется пс любому возможному варианту. Формировательь 23 и м пул ьса представляет собси ждуЩий мультивибрата),Декодер кодов РС функционирует следующим г,браэОМ,ДВОИЧНВЯ ПаСЛВДОВатЕЛЬНОСтЬ, СОДЕР- жашая к+ д элементов, паст",пает на ВКОД 2 ксистант и записыВается В кольц 8 Вой сдвигсвый регистр 16.Жесткие Знач 8 ния символов кбдОВОГО слова поступают иа первы 8 инфОрмзциснные Входы 20 и записываются В регистр 1, Одисвр 8 меннО значения надежнбсти символов принятОГО кОдоВОГО слова поступают на169020:., вторые информационныз с,хо/ы 21 и записываютсл В ре исгп 4 с Выходл которого значения надежности пО;тупают В блОк 5, ГДе ОпреДеллютсл индексы к + д наибОлее надежных симВОЛОВ кодовОГО слОва,Отобранные к + д индексы поступают изаписываютсл в реГистр 6, с разрядных выходов которого управляющие сигналы поступают на соответствующие разрядные входы управления перезаписью регистров 1 и 4, при этом с разрядных Выходов регистра 4 к + д значений надежности поступают на разрядные информационные входы регистра 7, с разрядных выходов которого выбранные значения надежности поступают на разрядные входы блока 8 порязрлдного сравнения, Одновременно с разрядных выходов регистра 1 Выбраннь а символь. кодо- ВОГО слова ПОступают на разрядные информационные Входы регистра 2.При невыполнении условия сравнения свыхода "Не равно" блока 8 на входы разрешения перезаписи регистров 1, 2 и 6 поступает сигнал управления, в результате происходит следующее процедура М 1),С разрядных выходов регистра 16, содержащих нулевые зле: енты последовательности, на разрядные Входы разрешения перезаписи в регистрах 2 и 6 гаступают сигналы, при этом с последовательных выходов регистров 2 и б разрешенные разряды поступают на первье входы жестких значений) и вторые инд .-,сиые) зходы блока 3 преобоазованил ;Оцов, Одновременно с последовательных Выходов регистра 1 на Входы компаратора 13 поступает кОДОВОе слово, принятое из алела связи.С Выходов блока 3 декодированный информационный набор поступает на входы регистра 10 декодирован ного слова, с выходов которого информационный набор поступает на Входы кодера 12 кода РС, с выходов которого кодовое слово поступает на другие входы компаратора 13, с выхода которого информация о посимвольном различии поступает на вход счетчика 14 числа различий.С выхода счетчика 14 число различийпоступает через первье входы 35 блока 15 управления на входы регистра 25 числа различий, и на первом цикле через разрядные входы поступает в регистр 26 копии, с последовательных выходов которых числа различий поступают на входы компаратора 27, с выходов котороо сигналили "=" или. поступает на входы сумматора 28. Кроме того, сигнал с выходакомпаратора 27 поступает через вентиль 34 на вход разрешения считывания регистра 25 и непосред;.;Ино через четвертый выход 4; блока 15- вход разрешения считывания регистраО, при этом через разрядные входы в ре; ,ср 11 копии записывается декодирован 5 .Ый ичформационный набор.С выхода сумматора 28 через первыйз.-:мкнутый контакт переключателя 29 сигнал поступает на вход счетчика 30 циклов.Затем выполняется следующее (процедура10 к: 2).С выходов счетчика 30 циклов сигналпес г пает на входы дешифратора 31 и через:.умматор 32 - на первый выход 38 блока 15правления, соединенный с входом управ 15 ленил сдвигом кольцевого регистра 16, притом происходит циклический сдвиг последовательности, а с выхода старшего разряда дешифоатора 31 сигнал поступает червзвторой выход 39 блока 15 управления на20: ход разрешения считывания регистра 11копии, с выхода которого на выход декодерапоступает декодированное кодовое слово, а, акже с выхода старшего разряда дешифратора 31 сигнал поступает через элемент 3325 задержки и третий выход 40 блока 15 управления на входы сброса всех регистров, кроме регистра 16.Пои выполнении условия сравнения свыхода "Равно блок 8 на управляющий30 .ход кл;оча 9 поступает сигнал, открывающий ключ 8. При атом содержимое первогоразряда регистра 16 поступает на вход бло:;а 17 сравненил с единицей,При вьполнении условия сравнения с35 выхода "Равно" олока 17 сигнал поступаетна входы разрешения перезаписи регистров 1, 2, б и через второй вход 36 блока 15правления на вход разрешения считывания регистра 25. Далее следует процедура40 ьПри невыполнении условия сравнения свыхода "Не равно" блока 17 сигнал поступает через третий вход 37 блока 15 управленияна вход формирователя 23 импульса, с вы 45 хода которого импульс поступает на управляющий Вход переключателя 29, и черезэлемент 24 задержки через замкнутый второй контакт переключателя 29 импульс поступает на вход счетчика 30 циклов; Далее50 следует процедура М 2.При использовании кода РС (31, 15) Вдекодере обеспечивается энергетическийвыигрыш кодирования 1,5 дБ по сравнениюс прототипом для случая, когда в канале с55 ортогональными сигналами вероятностьошибки Рс = 10 - 10 на кодовое слово,Формула изобретения1, Декодер кодов Рида-Соломона, содержащий регистр принятого кодового слова, информационные входы которого15 20 являются первыми информационными входами декодера, а разрядные выходы соединены с соответствующими информационными входами регистра выбранных кодовых символов, выходы которого подключены к первым входам блока преобразования кодов, выходы которого соединены с информационными входами регистра декодированного слова, регистр надежностей кодовых символов информационные, входы которого являются вторыми информационными входами декодера, а последовательные выходы соединены с входами блока определения индексов максимальных на. дежностей, Выходы котороГО подключены к информационным входам регистра вы. бранных индексов разрядные и последо. вательные выходы которого соединены соответственно с разрядными входами управления перезаписью регистра принятого кодового слова "и вторыми входами блока преобразования ОДОВ, О т л и ч а ю щ и йс я тем, что, с целью повышения помехозащищенности декодера, в него введены кольцевой сдвиговый регистр, регистр выбранных надежностей, блок поразрядного сравнения, ключ, блок сравнения с единицей, элементы развязки, одер кода Рида- Соломона, компаратор счетчика числа различий, регистр копии и блок управления, первый выход оороо Соеде с одо управления сдвигом кольцевого сдвигового реГистрз, информационные входы кОтороГО являются входами констз т декодера, а разрядные выходы подключены к разрядным входам управления перезаписью регистра выбранных кодовых символов и регистра выбранных индексов, последовательные выходы регистра принятоо кодового слова и регистра декодировзнного слова подключены соответственно непосредственно и через кодер кода Рида-Соломона к первым и Вторым Входам компзрзтсрз, выход кОторо" го соединен с входом счетчика числа различий, выходы которого подкл,очены к первым входам блока управления, второй выход которого соединен с входом разрешения считывания регистра копии, разрядные входы управления перезаписью регистра надежностей кодовых символов подключены к соответствующим разрядным выходам регистра выбранных индексов, разрядные выходы регистра надежностей кодовых символов соединены с информационными выходами регистра выбранных надежностей, Выходы котороГО подключены к соответствующим входам блока поразрядного сравнения, выходы "Не равно" и "Равно" КОТОРОГО СОЕДИНЕНЫ СООТВетстВЕННО С ВХО- дом первого элемента развязки и управляющим входом ключа, информационный вход которого подключен к выходу первого разряда кольцевого сдвигового регистра, выход ключа соединен с входом блока сравнения с единицей, выход "Равно" которого подключен к входу второго элемента развязки и второму входу блока управления, третий ВыхОд котороГО соединен с Входами Обнуления регистра выбранных надежностей, регистра надежностей кодовых символов, регистра выбранных индексов,регистра принятого кодового слова, регистра выбранных кодовых символов, регистра декодированного слова и пегистра копии,выходы элементов развязки объединены и подключены к входам разрешения перезаписи регистра выбранных индексов, регистра принятого кодового слова и регистра выбранных кодовых символов, выход "Не равно" блока сравнения с единицей соединен с третьим входом блока управления, четвертый выход которого подключен к входу разрешения считывания регистра декодированного слова, разрядные выходы которого соединены с информационнымивходами регистра копии, выход которого является выходом декодера,2. Декодер оо и. 1, отл ич а ю щи й сятем, что блок управления содержит компаратор, сумматоры, переключатель, формирователь импульса, элементы задержки. счетчик циклов, дешифратор, элемент развязки, регистр копии и регистр числа различий, информационные входы которого являются первыми входами блошка, а управляющий вход объединен с входом элемента развязки и является ТОрым водом блока, последовательные и разрядные выходы регистра числа различий соединены соответственно с первыми входами компараторз и входами регистра копии, выходы которого подключены к вторым входам компзратора, выходы "Больше" и "Равно" которогоаоединены с первым и вторым входами первого сумматора, выход которого подключен к первому информационному входу переключателя, вход формирователя импульса является третьим входом блока,выход формирователя импульса через первый элемент задержки и непосредственно соединен соответственно с вторым информационным и управляющим входами переКЛЮЧЗТЕЛЯ, ВЫХОД КОТОРОГО ПОДКЛЮЧ 8 Н К входу счетчика циклов, выходы которого соединены с входами дешифрзтооа, Выходы разрядов кОторОГО, кооме стзршеГО, подключены к входам ороо сумматора, вод котороГО является п 8 рвым ВыхОДОм блОка,выход старшего разряда дешифратора соеринен с входом второго элемента задержки. Заказ 3827 Тираж Подписное ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР 113035, Москва, Ж, Раушская наб., 4/5одственно-издательский комбинат "Патент", г. Ужгород, ул. Гагарина, 10 и является вторым выходом блока, выход второго элемента задержки является третьим выходом блока, выход "Меньше" компаратора подключен к третьему входу первогосумматора, входу элемента развязки и является четвертым выходом блока,