Пристрій для виявлення та виправлення помилок кодом ріда-соломона
Номер патенту: 14471
Опубліковано: 25.04.1997
Автори: Мартиненко Євген Іванович, Гулько Віталій Тарасович, Пономарчук Віталій Іванович, Авер'янова Тамара Федорівна
Формула / Реферат
Устройство для обнаружения и исправления ошибок кодом Рида-Соломона, содержащее блоки буферной памяти, первый вход первого блока буферной памяти подключен к информационной шине, отличающееся тем, что, с целью повышения быстродействия устройства, в него введены счетчик, арифметико-логический блок и блоки постоянной памяти, выход первого блока постоянной памяти соединен с первым входом счетчика, второй вход которого является тактовым входом устройства , выход счетчика соединен с входом второго блока постоянной памяти, первый выход которого соединен с первым входом первого блока постоянной памяти, второй выход второго блока постоянной памяти соединен с вторым входом первого блока буферной памяти, входами третьего блока постоянной памяти, второго блока буферной памяти и арифметико-логического блока, выход которого соединен с вторым входом первого блока постоянной памяти, третий вход которого является входом управления устройства, первый и второй входы-выходы третьего блока постоянной памяти соединены с первыми выходами-входами соответственно арифметико-логического блока и второго блока буферной памяти, третий вход-выход третьего блока постоянной памяти соединен с вторым выходом-входом арифметико-логического блока и подключен к информационной шине, четвертый вход-выход третьего блока постоянной памяти соединен с вторым выходом-входом второго блока буферной памяти и третьим входом первого блока буферной памяти,выход первого блока буферной памяти подключен к информационной шине.
Текст
Изобретение относится к автоматике и может применяться в системах с электронными дискретными устройствами передачи и хранения информации, где возможно возникновение пакетов ошибок. Устройство решает задачу обнаружения и исправления ошибок с использованием кода Рида-Соломона упрощенными средствами, существо 7 9 ts (•tf 5 > і p •I „і РПФ-К j J 1 s 1 Г L Г 7 1 1429324 Изобретение относится к электронС ным дискретным устройствам систем автоматики, телемеханики и вычислигде С - і-й - символ информационного тельной техники и предназначено для слова. использования в системах передачи и s Деление осуществляется по правилам хранения информации, где возможно деления полиномов. Первым приходит возникновение нескольких пакетов информационный символ С п . После расошибок. крытия скобок порождающий многочлен ЦеЛЬ изобретения - Повышение быСТ- fQ для исправления двух ошибок имеет родействия устройства. вид На чертеже представлена блок-схема предлагаемого устройства. Устройство содержит блок 1 постоянной памяти адресов перехода, счет- ^ Вычисление остатка от деления по чик 2, блок 3 постоянной памяти упправилу деления многочленов сводится равляющих сигналов, блок 4 буферной к следующим формулам: памяти, арифметико-логический блок 5, 7S блок 6 постоянной памяти, блок 7 буСі = С 1 М © Cjoi, Ї ферной памяти, информационную шину 8, 20 тактовый вход 9?шину 10 управления переходом, вход 11 управления, шину Т8 12 сигналов состояния, шину 13 адреса перехода на новые управляющие сигналы, адресную шину 14, шину 15 управ- 25 ляющих сигналов и двунаправленные шины 16-18, где С;_4 * последний пришедший симЕсли сигналы данных поступают по вол. шинам 8 и 16 из блока 5, то результат Декодирование начинается с вычисвыдается по шинам 17 и 18 в блок 7, 30 ления синдромов по схеме Ґорнера и, наоборот, если сигналы операндов поступают' из блока 7 по шинам 17 и C;©S ; 0 18, то табличный результат передается по шинам 8 и 16 в блок 5. Двунаправленная передача сигналов по шинам 8,16-18 для блока 6 осуществляется через ^ ^1 ~ C ( ©S 2 ot. 9 мультиплексоры. Блок 7 предназначен для приема, оперативного хранения S = C.CPSjol2» и выдачи по двунаправленным шинам 17, 18 промежуточных значений сигналов. где С^ - і-й символ информационного Блок 4 предназначен для хранения при- 40 слова; нятого слова, поступающего по дву- . о - примитивный элемент поля. б направленной шине 8. После вычисления синдромов S o , S,,, S 4 , S ? проверяется их равенство нулю, если все S; = 0 в то ошибок нет Устройство работает в двух режи45 и блок 3 выдает по шине 15 управлямах: кодирование и декодирования. ющий сигнал на выдачу информационного Кодирозание осуществляется путем слоя во внешнюю систему*, Если все де'ления информационного слова на поS'ijtO, то возможна одна ошибка и рождающий многочлен проверяется дополнительное условие q(x) • * х Длина порождающего многочлена зависит от количества исправляемых ошиxS, = борк. Для*-исправления двух оійибок Если все равенства выполняются, полином содержит первые четыре сомно -55 ,-сителя (al - примитивный элемект поля). то происходит одна ошибка, где S o является значением ошибки, а место Входную информацию также представляют ошибки вычисляется по формуле в виде полинома 1429324 где і - место ошибки. Если равенство не выполняется, то происходят две ошибки. Если больше ОДНОГО S; = О, НО НЄ ВСЄ S- = 0 , то количество ошибок больше двух и устройство отказывается от исправления. Если происходят две ошибки, то значения и адреса ошибок находятся из решения системы уравнений, которая для случая двух ошибок имеет вид: s =с © S, S, « где S_, S,, S , a 1 4 При умножении элемента поля Галуа на const сигналы, соответствующие значению элемента, поступают на вход блока 6, для которого они являются .. адресами, по которым записаны коды, соответствующие значению элемента, умноженного на const, где і и j - адреса ошибок; С; и CJ - значения ошибок. Исправление происходит по формуле /1 ^ где С; - неисправленный символ; С - исправленный символ. Для улучшения корректирующей способности кода используется код с перемножением, по которому (Информационное слово разделяется на два слова 20 по принципу один символ в одно слово, следующий во второе и т.д. - вычисленные '0-2 I .синдромы; j Су и С: - значения-ошибок; 25 і и j - адреса ошибочных где С. - информационный символ, идусимволов; щий в первое слово; е£ - примитивный элеС. - информационный символ, мент поля Галуа. Решая эту систему уравнений, нахо*- 30 идущий во второе слово. дят значения ошибок С; и С- и адреса Каждое слово кодируется и декодинеисправленных символов і и j . Вычисруется как независимое, это позволяления производятся без использования ет существенно улучшить параметры умножителей и сумматоров по модулю устройства по исправлению пакетов основания кода. Для вычисления ис35 ошибок без его усложнения. пользуется свойство, по которому В режиме кодирования на вход 11 каждый элемент можно представить как управления поступает признак кодиростепень примитивного элемента поля вания (уровень 0 ) , который совместно Cj = ЫГ с кодовыми комбинациями, поступающими где С: - j-й - элемент по40 по шинам 10 и 12 соответственно из ля; і - степень примитивного элеблоков 3 и 5, является адресом выбомента. ра из блока 1 начального адреса ко в ~ В поле заданы две операции: сложедирования, поступающего по шине 13 ние по mod 2 и умножение. Операция на счетчик 2. Со счетчика 2 по шине умножения сводится к сложению степеней примитивного элемента. При умно- 45 14 адрес без изменения выдается в блок 3, по которому в нем записаны женин двух элементов поля Галуа сигуправляющие сигналы выполнения первой налы, соответствующие значению каждооперации, результатом которой являго элемента, поступают на яходы блока 6, для которого они являются адресами • ется обработка первого информаци50 онного символа. Первый информационтаблиц логарифмов. По этим адресам ный символ по информационной тине 8 записаны коды, соответствующие покапоступает1 в блок 5, откуда без измезателям степеней примитивных элеменнения записывается через блок 6 в тов. Эти коды поступают на вход арифблок•7. метико-логического блока 5, где они складываются, и результат поступает 55 на вход блока 6 (таблицы антилогарифАдреса управляющих сигналов для мов), по которому считываются сигнаобработки последующих информационных лы, представляющие значение резульсимволов выдаются последовательно со тата умножения двух элементов. счетчика 2 с частотой тактовых сигна 1429324 лов, поступающих на счетный вход управляющими символами, поступающими счетчика 2 по кодовой шине 9. из блока 6 по шине Ї5. Дальнейшую работу рассмотрим на С приходом последнего символа запримере обработки (і-4)-го информаканчивается вычисление синдромов, и ционного символа. Перед приходом с начинается определение возможного (ї-4)-го информационного символа в количества ошибок в информационном блок 7 записаны вычисленные ранее слове. Для проверки на равенство нулю і-й, (і-1)-й, (і-2)-й, (і-З)-й симвосиндром из блока 7 записывается в лыц По информационной шине 8 (і-4)-й блок 5. В зависимости от того, равен символ поступает в блок 5. Из блока 7 fO он нулю или не равен, по шине 12 . по шине 17 и 18 поступает С' на вход соответствующая кодовая комбинация блока 6, Он является адресом, по ковыдается с выхода блока 5 на вход торому 6записан результат умножения блока 1, и происходит формирование С> х of . Из блока 6 этот результат нового адреса управляющих сигналов. по шине 16 поступает в блок 5, где 15 Для проверки равенства, например, производится операция сложения по S o х $±. - S^ S O H S^ считываются из mod 2. Результат операции поступает блока 7 соответственно по шинам 17 по шине 17 или 18 и записывается без и 18 и поступают на вход блока 6, изменения в блок 7. где они являются адресами таблицы Управление описанным процессом 20 логарифмов. Из блока 6 считанное из адресов таблицы логарифмов значение вычисления осуществляется управляющистепеней примитивного элемента постуми сигналами» поступающими по шине 15 пает по шинам 8 и 16 соответственно из блока 3, Аналогично вычисляются в блок 5, где происходит их сложение. новые значения С,*_г, С ^ м , С;. Если поступивший (і~4)-й символ последний, 25 Результат сложения из блока 5 по шине 8 или 16 поступает на вход блока 6 то вновь вычисленные символы С,'_з , как адрес таблицы антилогарифмов. С ^ , С,- м > С; являются контрольными Считанное значение записывается по символами информационного слова, шине 17 или 18 в блок 7. Аналогично которые поступают из блока 5 по шине 8 во внешнюю систему. 30 вычисляется S ( . Для проверки-равенства полученные значения считываются из блока 7 в блок 5, где происходит В режиме декодирования, по шине 11 сложение по mod 2. В зависимости от 'поступает уровень логической "і". результата операции соответствующий Выбор начального адреса режима декодирования аналогичен режиму кодироэ 5 код поступает по шине 12 на вход блока 12 и происходит формирование -вания. По шине 8 в устройство постунового адреса управляющих сигналов. пает информационное слово с контрольНайденный адрес неисправного символа ными символами. Первый символ без поступает по шине 17 в блок 4, откуда изменений записывается в блок 7. Рассмотрим вычисления синдромов S o , S ( , 40 неисправный символ по шине 8 поступает в блок 5, где происходит корректиS*» S3 с приходом і-го символа. В і ровка по формуле блоке 7 записаны вычисленные ранее значения S e , S ( , S a , S3« По информационной шине 8 і-й символ поступает С; = Cf © С? , • в блок 5. Из блока 7 по шине 17 или ^5 18 предыдущее значение синдрома посгде С; - неисправленный символ, поступает на вход блока б, где оно являтупивший из блока 4; ется адресом таблицы умножения синд- • С- - значение ошибки, поступаюрома на соответствующую const. Вычисщее из блока 7 в блок 5j ления производятся по описанной схеме С; - исправленный символ. Горнера» В блоке 5 производится опе- 50 рация сложения по mod 2 над пришедшим Операция исправления осуществлясимволом и ранее вычисленным синдроется по управляющим сигналам, постумом, умноженным па const, поступившим пающим по шине 15 из блока 3. Исправпо шине 16 из блока 6. Результат выленный символ по шине 8 записывается числения записывается в блок 7, Зна- 55 из блока 5 в блок 4, После исправлен чение операций блока 5, выбор табния всех ошибок слово из -блока 4 лиц в блоке 6 Р выбор адресов в блоке выдается по шине 8 во внешнюю сис7, направление передачи определяются тему. 1429324 8 Ф о р м у л а и з о б р е т е н и я блока постоянной памяти, второго блоУстройство для обнаружения и и с ка буферной памяти и арифметико-лоправления ошибок кодом Рида-Соломона, гического блока, выход которого соесодержащее блоки буферной памяти, динен с вторым входом первого блока первый вход первого блока буферной постоянной памяти, третий вход котопамяти подключен к информационной рого является входом управления устшине, о т л и ч а ю щ е е с я тем, ройства, первый и второй входы-вычто,, с целью повышения быстродействия ходы третьего блока постоянной памяти . соединены с первыми выходами-входами устройства» в него введены счетчик, арифметико-логический блок и блоки 10 соответственно арифметико-логического постоянной памяти, выход первого блока и второго блока буферной памяблока постоянной памяти соединен с ти, третий вход-выход третьего блока первым входом счетчика, второй вход постоянной памяти соединен с вторым которого является тактовым входом выходом-входом арифметико-логическоустройства» выход счетчика соединен Ї5 го блока и подключен к информационной с входом второго блока постоянной шине, четвертый вход-выход третьего памяти, первый выход которого соедиблока постоянной памяти соединен с нен с первым входом первого блока вторым выходом-входом второго блока постоянной памяти, второй выход втобуферной памяти и третьим входом рого блока постоянной памяти соеди- 20 первого блока буферной памяти, выход нен с вторым входом первого блока первого блока буферной памяти подклюбуферной памяти, входами третьего чен к информационной шине. h V л И4 *» Я U It» Редактор 0. Головач Іаказ 5144/56 iJJ, V Чн Ч, /L 1 *-~J*l> Составитель С. Берестевич Техред Л.Олийнык Корректор С. Черни Тираж 929 Подписное ВНИИЇЇИ Государственного комитета СССР по делам изобретений и открытий 113035, Москва, Ж-35, Раушская н а б . , д. 4/5 Производственно-полиграфическое предприятие, г. Ужгород, ул, Проектная, 4
ДивитисяДодаткова інформація
Назва патенту англійськоюDevice for error detection and correction of errors by reed-solomon code
Автори англійськоюMartynenko Yevhen Ivanovych, Aver'ianova Tamara Fedorivna, Gulko Vitalii Tarasovych, Ponomarchuk Vitalii Ivanovych
Назва патенту російськоюУстройство для обнаружения и исправления ошибок кодом рида-соломона
Автори російськоюМартыненко Евгений Иванович, Аверьянова Тамара Федоровна, Гулько Виталий Тарасович, Пономарчук Виталий Иванович
МПК / Мітки
МПК: H03M 13/00
Мітки: виявлення, помилок, кодом, виправлення, ріда-соломона, пристрій
Код посилання
<a href="https://ua.patents.su/6-14471-pristrijj-dlya-viyavlennya-ta-vipravlennya-pomilok-kodom-rida-solomona.html" target="_blank" rel="follow" title="База патентів України">Пристрій для виявлення та виправлення помилок кодом ріда-соломона</a>
Попередній патент: Пристрій для зчитування циліндричних магнітних доменів
Наступний патент: Плавкий запобіжник
Випадковий патент: Мінеральна добавка для жуйних тварин