Устройство для обнаружения и исправления ошибок кодом рида соломона

(ю 4 Н 0 НИ ДЛЯ ОБНАР БОК КОДОМ ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ ПИСАНИЕ ИЗОБРЕ АВТОРСКОМУ С 8 ИДЕТЕЛЬСТВУ(56) Авторское свидетельство СССРУ 1381719, кл. Н 03 М 13/00,27.02.87.(54) УСТРОЙСТВО УЖЕНИЯ ИИСПРАВЛЕНИЯ ОШИ РИДА-СОЛОМОНА(57) Изобретение относится к автоматике и может применяться в системах с электронными дискретными устройствами передачи и хранения информации, где возможно возникновениепакетов ошибок. Устройство решаетзадачу обнаружения и исправления ошибок с использованием кода Рида"Соло. мона упрощенными средствами, существо которых состоит в том, что все операции при кодировании и декодированиисводятся к ограниченному набору операций: сложенияпо шой 2, сложению,вычитанию и использованию табличныхметодов, таких как таблицы логарифмов, антилогарифмов, умножения насопзС, извлечения корней уравнения,Устройство содержит блок постояннойпамяти адресов перехода 1, счетчик 2 тблок постоянной памяти управляющихсигналов 3, блок буферной памяти 4,арифметико-,логический блок 5,.блок постоянной памяти 6, блок буферной памяти 7, информационную шину 8,тактовый вход 9, шину управления пе-реходом 10, вход управления 11, шинусигналов состояния 1 д, шину адРеса Щперехода на новые управляющие сигналы 13, адресную шину 14 управляющихсигналов 15, двунаправленные шины16, 17, 18. 1 ил.8, щ С;9806 1 Изобретение относится к электрон ным дискретным устройствам систем Эвтоматики, телемеханики и вычислительной техники и предназначено для Использования в системах передачи и хранения информации, где возможно возникновение нескольких пакетов ошибок.Цель изобретения - повышение быст О родействия устройства.На чертеже представлена блок-схема предлагаемого устройства.Устройство содержит блок 1 постоиной памяти адресов перехода, счетик 2, блок 3 постоянной памяти упавляющих сигналов, блок 4 буферной памяти, арифметико-логический блок 5, блок 6 постоянной памяти, блок 7 бу.:ферной памяти, информационную шину 8, 2 О тактовый вход 9,шину 10 управления переходом, вход 11 управления, шину :,12 сигналов состояния, шину 13 адреса ,"перехода на новые управлякщие сигна,лы, адресную шину 14, шину 15 управ ,:ляющих сигналов и двунаправленные шины 16-18.Если сигналы данных поступают по шинам 8 и 16 иэ блока 5, то результат ,выдается по шинам 17 и 18 в блок 7, 30 .и, наоборот, если сигналы операндов поступаютиз блока 7 по шинам 17 и , 18, то табличный результат передается по шинам 8 и 16 в блок 5. Двунаправленная передача сигналов по шинам 8,16-18 для блока 6 осуществляется через мультиплексоры. Блок 7 предназначендля приема, оперативного хранения и выдачи по двунаправленным шинам 17, 18 промежуточных значений сигналов. Блок 4 предназначен для хранения принятого слова, поступающего по двунаправленной шине 8. Устройство работает в двух режимах: кодирования и декодирования.Кодирование осуществляется путем деления информационного слова на порождающий многочлен с(х) = (х 91) (х 9 о) (х Ы,ф)(хэо ).л 5 О где С - -й - символ информационногослова.Деление осуществляется по правилам деления полиномов. Первым приходит информационный символ С, После раскрытия скобок порождающий многочлен для исправления двух ошибок имеет вид ц(х) х щ хз Ря хЫф 44 у х РЮКф. Вычисление остатка от деления поправилу деления многочленов сводитсяк следующим формулам: где С;4 - последний пришедший символ.Декодирование начинается с вычисления синдромов по схеме Горнера 8, - С;88 С;68 еСз 1Я СЮЯьсгде С - х-й символ информационногослова;Ы, - примитивный элемент поля.После вычисления синдромов 8, 8 8 8проверяется их равенство Фнулю, если все 8, = О, то ошибок нет и блок 3 выдает по шине 15 управляющий сигнал на выдачу информационного слоя во внешнюю систему Если все 8, ф О, то возможна одна ошибка и проверяется дополнительное условиеДлина порождающего многочлена зависит от количества исправляемых ошиборк. Для- исправления двух ошибок полином содержит первые четыре сомножителя (Ы в ,примитивный элемент поля). Входную информацию также представляют в виде полинома фх Если все равенства выполняются,то происходит одна ошибка, где Я. является значением ошибкИ, а местоошибки вычисляется по формулефоф где д - место ошибки.Если равенство не выполняется, то происходят две ошибки. Если больше одного Я; = О, но не все Я; = О, то количество ошибок больше двух и устройство отказывается от исправления. Если происходят две ошибки, то значения и адреса ошибок находятся из решения системы уравнений, которая для случая двух ошибок имеет вид: С;Ю С 1 СЕС; Ы, синдромы;С - значения ошибокУ- адреса ошибочныхсимволовв примитивн элемент поля Галуа.Решая эту систему уравнений, нахо дят значения ошибок С; и С и адреса неисправленных символови 3. Вычисления производятся без использования умножителей и сумматоров по модулю основания кода. Для вычисления используется свойство, по которому каждый элемент можно представить как степень примитивного элемента поля С = оГгде С - 3-й - элемент поф 3ля; д - степень примитивного элемента.и Си В поле заданы две операции: сложение по шой 2 и умножение. Операция умножения сводится к сложению степеней примитивного элемента. При умножении двух элементов поля Галуа сигналы, соответствующие значению каждого элемента, поступают на входы блока 6, для которого они являются адресами таблиц логарифмов. По этим адресам записаны коды, соответствующие показателям степеней примитивных элементов. Эти коды поступают .на вход арифметико-логического .блока 5, где они складываются, и результат поступает на вход блока 6 (таблицы антилогарифмов), по которому считываются сигналы, представляющие значение результата умножения двух элементов.где С - неисправленный символ;ФС - исправленный символ,1Для улучшения корректирующей способности кода используется код с перемножением, по которому информационное слово разделяется на два слова0 по принципу один символ в одно слово,следующий во второе и т.д,,С, С 5- информационныи символ, идущий в первое слово;С- информационный символ,З 0идущий во второе слово.Каждое слово кодируется .и декодируется как независимое, это позволя,ет существенно улучшить параметрыустройства по исправлению пакетов35 ошибок без его усложнения,В режиме кодирования на вход 11управления поступает признак кодирования (уровень 0), который совместнос кодовыми комбинациями, поступающими40 по шинам 10 и 12 соответственно изблоков 3 и 5, является адресом выбора из блока 1 начального адреса кодирования, поступающего по шине 13на счетчик 2. Со счетчика 2 по шине45 14 адрес без изменения вьдается вблок 3, по которому в нем записаныуправляющие сигналы выполнения первойоперации, результатом которой явля ется обработка первого информаци 5 О онного символа. Первый информационный символ по информационной шине 8поступает в блок 5, откуда беэ изменения записывается через блок 6 вблок 7,55 ля Адрес обработк символов счетчика сигналоинформаедователтактовых упр авляющих последующих вьдаются по 2 с частото ционныхьно сосигнаПри умножении элемента поля Галуана сопят сигналы соответствующиезначению элемента, поступают на входблока 6, для которого они являются:адресами, по которым записаны коды,соответствующие значению элемента,умноженного на сопят, где х и 1 - ад-,реса ошибок; С, и С - значения ошибок. Исправление пройсходит по фор муле5 1429324 6лов, поступающих на счетный вход управляющими символами, поступающимисчетчика 2 по кодовой шине 9. из блока 6 по шине 15,йДальне шую ра отуб рассмотрим на С приходом последнего символа эапримере обработки (-4)-го информа- канчивается вычисление синдромов.иначинается определение возможного(-4)-го информационного символа в количества ошибок в информационномблок 7 записаны вычисленные ранее . слове. Для проверки на равенство нулю1 й, (1-1)-й, (х)-й (-3)-й симво- синдром из блоха 7 записывается в1пЬь По информационной шине 8 (х)"й блок 5. В зависимости от того, равенсюс мвол поступает в блок 5. Из блока 7 10 он нулю или не равен, по шине 12шине 17 и 18 поступает С; на вход соответствующая кодовая комбинация6 Он является адресом, по ко- выдается с выхода блока 5 на входока . н являит фо ованиеорому записан результат умножения блока 1, и происходит формирнового адреса управляющих сигналов.о шине 16 поступает в блок 5, где 15 Для проверки равенства, например,фоизводит"я операция сложения по Я х Б, -х Б, = Б Я н Б считываются изпой 2. Результат операции поступае". блока 7 соответственно по шинам 17о шине " илио шине "7 или 18 и записывается без и 18 и поступают на вход блока 6,ц б 7изменения в лок где они являются адресами таблицыУправление описанным процессом 20 логарифмов. Из блока 6 считанное изфз бло са 3, Аналогично вычисляютсяычислепия осуществляется управляющи- адресов таблицы логарифмов значение. ающимн по шине 15 степеней примитивного элемента посту-сигналами, поступающими попает по шинам 8 и 16 о т6 соответственноаС С С . Если в блок 5, где происходит их сложение.оьые знаяепия С; ,б ка 5 по шинеоступивши .- - си ооступивший (-4)-й символ последний, 25 Резул.:тат, сложения из блока по шинеФ ь вычисленные символы С; , 8 или 16 поступает на вход блока 6о вновь в -з юС , С; являются контрольными как адрес таблицы антило р фсимволами информационного слова, Считанное значенние записывается поКоторые поступают из блока 5 по шине шине .17. 7 или 18 в блок 7. Аналогичново внешнюю систему. З 7 вычисляется Б Для проверки-равенства полученные значения считываютсяВ режиме декодирования,по шине 11из блока 7 в блок 5, где происходитИсложение по шой 2. В зависимости отпоступает уровень логической 1Ьыбор начального адреса режима деко- результата операции соответствующийдирования аналогичен режиму кодиро код пос уания. По шине 8 в устройство посту- блока 12 и происходит формированиефания. о непает информационное слово с контроль- нового адрреса п авляющих сигналов.ными символами, Первый символ без Найденнь дрй а ес неисправного символаий записывается в блок 7. Рас- поступает по шине 17 в блок 4, откуда.изменени эаписсмотрим вычисления синдромов Б, Я о неисправный символ по шине уо8 пост паЯ . Я риходом -го символа. В . ет в блок 5, где происходит корректиФф 3блоке 7 записаны вычисленные ранее ровка по формулезначения Б, Я, Б, Б . По информафционной шине 8 х-й символ поступаетв блок 5. Из блока 7 по шине 17 или18 ее значение синдрома пос- где С, - неисправленный символ, поспредьщущб 4тупает на вход блока 6, где оно явля- тупивший из блокается адресом таблицы умножения синд- С; - значение ошибки, поступаюрома на соответствующую сопз. Вычисения производятся по описанной схеме 5 О С; - ижравленж жмвы,Горнера, В блоке 5 производится опеа я сложения по шой 2 над пришедшим Операция исправления осуществлясимволом и ранее вычисленным синдро" ется по управ ющавляющим сигналам постуФмом, умноженным на сосопзС поступившим пающим по шине 15 иэ блока 3. Исправпо шине 1 из лока . ез16 б 6 Р ультат вы- ленный символ по шине 8 записывается55числения записывается в лоыв ется в блок 7 Зна- иэ блока 5 в блок 4. После исправле-чение операщФ локащФ блока 5 выбор таб- ния всех ошибок слово из блока 4лиц в блоке 6, выбор адресов в блоке выдается по шине 8 во внешнюю сис 7, направление передачи определяются тему.Составитель С. БерестевичРедактор О. Головач Техред Л.Олийнык Корректор С. Черни Заказ 5144/5 б , Тираж 929 ПодписноеВНЩПИ Государственного комитета СССР.по делам изобретений и открытий113035, Москва, Ж, Раушская наб д, 4/5 Производственно-полиграфическое предприятие, г. Ужгород, ул. Проектная, 4 7 142 Формула изобретенияУстройство для обнаружения и исправления ошибок кодом Рида-Соломона, содержащее блоки буферной памяти, первый вход первого блока буферной памяти подключен к информационной шине, о т л и ч а ю щ е е с я тем, что, с. целью повышения быстродействия устройства, в него введены счетчик, арифметико-логический блок и блоки постоянной памяти, выход первого блока постоянной памяти соединен с первым входом счетчика, второй вход которого является тактовым входом устройства, выход счетчика соединен с входом второго блока постоянной памяти, первый выход которого соединен с первым входом первого блока постоянной памяти, второй выход второго блока постоянной памяти соединен с вторым входом первого блока буферной памяти, входами третьего 9324 8блока постоянной памяти, второго блока буферной памяти и арифметико"логического блока, выход которого соединен с вторым входом первого блокапостоянной памяти, третий вход которого является входом управления устройства, первый и второй входы-выходы третьего блока постоянной памятисоединены с первыми выходами-входами 10 соответственно арифметико-логическогоблока и второго блока буферной памяти, третий вход-выход третьего блокапостоянной памяти соединен с вторымвыходом-входом арифметико-логическо го блока и подключен к информационнойшине, четвертый вход-выход третьегоблока постоянной памяти соединен свторым выходом-входом второго блокабуферной памяти и третьим входом 20 первого блока буферной памяти, выходпервого блока буферной памяти подключен к информационной шине,