Устройство для декодирования с коррекцией ошибок

Изобретение относится к вычислительной технике и может быть ис-,пользовано в системах передачи ихранения дискретной инЬормации,Цель изобретения - повышение надежности функционирования,На фиг. 1 приведена блок-схемаустройствами на Аиг. 2-4 - Ьункциональные схемы соответственно формирователя проверочных символов, блокаисправления ошибки и блока управле -ния; на Ьиг. 5 - временные диаграм,мы работы устройства.Устройство для декодирования скоррекцией ошибок содержит входнойрегистр 1, первый 2 и второй 3 формирователи проверочного символа, буЬерные регистры 4-7 .с первого почетвертый, сумматор 8, блок 9 исправ.ления ошибок., блок 10 ключей и блок11 управления. Устройство имеет так-,же инЬормационный 12 и тактовый 13входы и выход 14,Входной регистр 1 является регистром сдвига с числом разрядов(2 +4) ш, где ш - степень неприводимого многочлена в поле СР (2 ). Выходы разрядов с первого по тп-й являются первыми выходами регистра 1,выходы разрядов с (2 +3)-го по 1(2 + 30+3) н 1-го - его вторыми выходами,а выход последнего разряда - третьимвыходом регистра 1.формирователи 2 и 3 служат дляформирования соответственно первогои второго проверочного символов иимеют одинаковое выполнение. Каждыйиэ них (фиг, 2) содержит буферныерегистры 15-18 с первого по четвертый, вычитатель 19, сумматор 20 и 40преобразователь 21 кода, Один извходов вычислителя соединен с шиной22 источника логической единицы. НаАиг. 2 обозначены. также информационные и управляющие входы 23 и 24 45и выходы 25 формирователя.Блок 9 исправления ошибок (Ьиг.3)выполнен на первом 26 и втором 27буЬерных регистрах, вычитателе 28,преобразователе 29 кода и сумматоре 5030. На фиг, 3 обозначены первые 31 ивторые 32 информационные входы, управляющие входы 33 и выход 34,Блок 10 ключей представляет собой, напримеР, четыре двухвходовыхэлемента И, выходы которых объедииены на элементе ИЛИ.Блок 11 управления (фиг, 4) содержит первый 35 и второй 36 элементы И-НЕ, первый 37 и второй 38 буферные регистры, счетчик 39, первый40 и второй 41 вычитатели, .первый42 и второй 43 элементы сравнения,первый 44 и второй 45 дешифраторы,преобразователь 46 кода, сумматор47, первый 48 и второй 49 элементыИЛИ, генератор 50 управляющих импуль.сов, элементы И 51-54 с первого почетвертый, На фиг. 4, кроме того,обозначены первый 55, второй 56, .третий 57 и четвертый 58 входы и выходы 59-63 с первого по пятый,Сумматор 8, а также сумматоры 20,30 и 47 соответствующих блоков представляют собой сумматоры по модулю2 - 1.Вычитатели 19, 28, 40 и 41 являются вычитателями по модулю 2 -1, Вычитатель 19 в каждом Ьормирователе 2 и3 выполнен на сумматоре с входомпринудительного вычитания единицы,который соединен с шиной 22.Преобразователи 21, 29 и 46 кода,осуществляют над входной величиной7, преобразования Ы 1 =10+К где К еЕ СР(2 ) - примитивный элемент; О+суммирование в поле СР(2),Первый и второй выходы первогоэлемента 42 сравнения в блоке 11 управления (фиг. 4) являются выходамисоответственно неравенства и равенства входных величин, Выход второгоэлемента 43 сравнения является выходом равенства входных величин,Первые выходы первого дешифратора44 соответствуют значениям сигналовна выходах счетчика 39, лежащим впределах от нуля до 2 -2 включительно, Второй, третий и четвертый выходы первого дешиЬратора 44 соответствуют значениям на выходах счетчика 39, равным 2 -1, 2 и 2 +1.Выходы второго дешиАратора 45 спервого по четвертый соответствуютзначениям О, 1, 2 и 3 (в двоичномкоде) на его входах.Генератор 50 представляет собойраспределитель импульсов и узел логических элементов, обеспечивающийформирование управляюших импульсовв требуемой последовательности.На Ьиг. 5 изображены тактовыеимпульсы (ТИ) по циклам и соответствующие управляющие сигналы 3 дляслучая, когда ш=4.Принцип действия устройства декодирования с коррекцией ошибки заключается в следующем.(4)55 Информация, подлежащая декодированию, разбита на блоки по 2 шразрядных информационных символов и два проверочных символа в каждом блоке, являющихся показателями степени примитивного элементаоьЕСГ(2 )- корня неприводимого многочлена Е(х) степени ш,Обозначим информационные символы К;, 1=02 -1, проверочные символы К , КПервый проверочный символ кй г =Я ж =о О+М О+О+к "-, Ы 51 О где О+ и,7 - суммирование в полеСР(2 ),Бверел 1 функцию Ч 7(2) такую,что оа (7) = 19 оС, Тодаст,о (+) "1 -. 20О+й =ск. "." "=сс , и в общем случаеЫ, =Ж(+7 М =К1" К), илиа, ак; кЬ(а 1 кпереходя к показателям степеней а; ==К;+р(а; 1 -К;), Обозначим Ь; =а, -К.,25тогда а=К +(Ь; ), и а. =К +(Ь, ),откуда Ь; =К -К;.+ср(Ь;., ) . (2)Уравнение (2) является итерационной формулой для получения первого проверочного символа,Начальные условия: КО 1 (3)Вычисления по формулам (2) и (3),т.е. операции сложения и вычитания,осуществляются по модули (2 -1).При эт 1 ом нужно иметь в виду, чтоК =2 -1 не определено в кольце по1Щмодулю (2 -1).Поэтому (2"-1)+а=2 -1; где а - любой элемент кольца.При этом сс "=О и К =2 -1 изы маются из суммы (1), для чего в блок 11 управления введена схема И-НЕ 35, выдающая запрет на выдачу управляющих сигналов в генератор 50 управляющих импульсов. 50Второй проверочный символ получают.из соотношения=К -К,-1+Ч(Ь, ) Проверочные символы по формулам (1) и (4) формируются в кодирующем устройстве, Проверочные символы, формируемые в устройстве декодирования с коррекцией ошибок, обозначимК 1 - первый проверочный символ; К,7- второй проверочный символ; 2 -2причем с 2р (к,Проверочные символы, сформированные в кодируищем устройстве и принятые в устройстве декодирования с коррекцией ошибок, обозначимК 1 - первый проверочный символ;1 Г,- второй проверочный символ.1. Если при передаче информации в устройство декодирования с коррек цией ошибок ошибок не было, тоЛК 1 -Кгт,При этом синдромы ошибок Ь 1 Кг Кг 171 5,=м =м, Яо. =0 7 5 2 г+дк 2 +1 К п 1 К 111 р 2"о+ С г"ф: огОбозначим ос=О .Тогда Ь, = оа , Ь =К =К . (8)г 2 22, Если ошибка возникла в-м сим -воле информационной части Я=О2 -2);то2 117Ь 1 К К, К, . К5,=оь =(й О К = О ОМ О1 с 0,1ко+Во к ко+Бо коар(В)Я,Э ОЬ О+ о. фо 9 о, =о,1=0 1 Ф2 -2Мг "г"+1 Кг" + К;+1 К+5,=о .Ы О+и, = М, Ус Я0,12-гк к,+ ко+Мо кц(ооО+о О+ ос О+с:мО+1:0,1 Ф 1Э акг1292189 30 К,=Ь, +Ср(К, - Ь,). 1 Нет Нет Нет 3 (2 -1)-й Да Нет 45 л2 -йДа Да Да 5 (2 +1)-й Нет Да ф:0 Так как ошибка произошла в.информационной. части, то принятые проверочные символы не имеют ошибок.Следовательнод 2 д 2 к 2 к р+ фЮБг-К -0 +А Об илиЬ, =+К,+(Г )=Ь,+(К -Ь,), (11)Тогда из выражений (9) и (1) находим номер ошибочной позиции г +Ч(К гд 2)Исправление ошибки производится следующим образом,По номеру ошибочной позиции из входного сдвигового регистра 1 (позиция 2 +3) на регистр 26 блока 9 исправления ошибки записывается испорченный символ К=К +3.Из формулы (9)од =кО+ сф откуда м, = дфоп,к,д се(Гр-д,) (13) Данный алгоритм и реализуетблок 9.3, Если ошибка происходит на(2 -1)-й позиции 8=2 -1), то й)10 ОСд од или Ь =К, причем К =К , так как г"г г ошибка - в информационной части. Следовательно Ь, 1 оэ, Ь =К ш (14) Исправление ошибки аналогично п, 2. 4. Ошибка в первом проверочном символе (К ).- лВ этом случае К К иг"5:МО+м=о+Ч(, 41гффф гф+у гф г5,=юг аы г "=Ы г Од г Ог" г"0+0 = с так как К=КСледовательйоЬ, гм, д,1 Кг, Ь, К т (15)так как Кг =КгИсправление ошибки заключается взамене испорченного символа К навновь сформированный (правильйый)проверочный символ Кг.5. Ошибка во втором проверочном 20 символе (К ). В этом случае синдром по первому проверочному символуБ, =О, а по второму Следовательно Ь, =со, Ь фКгГЙ фИсправление ошибки2"и гф г фтак как К 2-=Кг Все варианты возможных одиночных ошибок сведены в таблицу. 35 ъ /,Вари- Ошибка в по- басю Л ФК 6; - К 2 г 2 ант зиции40 .2 -й (Я:О 2-2) Да Да Нет 50Устройство работает следующимобразом.На вход 12 устройства поступаютблоки кодовых слов по 72 разряда вкаждом (64 разряда информационных,558 проверочных) в сопровождении тактовых импульсов (ТИ),Первые 4 такта следует нулевойцикл, в течение которого заполняют 1292189ся первые 4 разряда. входного регистра 1, Затем следует 1-й цикл (5-8такты), в котором, если информационный символ не равен 2 -1 (15),производится запись на регистры 15формирователей 2 и 3 первого символа информации по сигналу 11 и егоперепись на регистры 16 - по сигналами 3 соответственно. Еслиинформационный символ равен "15" 1 О(1111), то регистры 15 обнуляются и элемент И-НЕ 35 блока 11 управ.ления выдает запрет ("0") на генератор 50 управляющих сигналов, запрещающий выдачу управляющих сигналов на регистры 16-18 формирователя 2,В этом случае формирователь 3работает в режиме вычитания "1"(формула (5 с шины 22 вычитателя19,В следующем, втором,. цикле (912-й такты) производится запись нарегистры 15 второго информационного символа по сигналу (3 вычитаниеиз содержимого Крегистров 16, содержимого К регистров 15 на вычитателях 19, сложение полученных результатов с "нулем" регистров 17 насумматорах 20 изапись результатов 30на регистры 18 по сигналам3 и6, Далее по , сигналам Д 2 и 5производится передача второго информационного символа К на регистры16 и одновременно по сигналам 8 4 и7 - передача содержимого регистров.18 с преобразованием его по формулеж =1 ОР(ав преобразователях 21 нарегистры 17.Третий цикл аналогичен второму, 40за исключением того, что при сложении на сумматорах 20 оба операндав общем случае отличны от нуля.Остальные циклы (4-15-й) аналогичны третьему. При этом в 15-м цикле на регистр 18 формирователя 3по сигналу 6 записывается сформированный второй проверочный символК который по сигналу 8 переписывается на регистр 5. 50В 16-м цикле по сигналу 33 нарегистр 18 формирователя 2 записывается сформированный первый провероч"ный символ К,ь, который по сигналу9 переписывается на регистр 4 искладывается с содержимым регистра5.на сумматоре 8, Результат сложения записывается на регистр 7 посигналу10В 17-м цикле на регистр 15 дюрми.рователя 2 по сигналу 31 поступаетпервый проверочный символ К, , который суммируется с содержилым (Кц)регистра 17 на сумматоре 20. Результат суммь по сигналу3 записывается на регистр 18 и затем по сигналу 11 - на регистр 6,В 18-м цикле (нулевой цикл следующего блока информации) на регистр15 формирователя 3 по сигналу1записывается второй проверочный символ К который суммируется с содерилжимым (К, ) регистра 17 на сумматоре20. Результат суммы Ь по сигналу6 записывается на регистр 18,В 16-м и 17-и циклах сигнал (61блокируется блоком 11 управления наформирователь 3, а в 18-м цикле - наформирователь 2,1В 17-м цикле по сигналу 12 первый проверочный символ К, с регистра 1 переписывается на регистр 37блока 11, а в 18-м К 1 цикле содержимое (Ь ) регистра 18 формирователя3 переписывается на регистр 38 блока 11 по сигналу13.Если ошибка произошла в 1 -м символе информационной части Я=О14), то в соответствии с формулой12) на вычитателе 40 осуществляется получение разности К, -Ь, а на вычитателе 41 - разности Ь -ь,. С вычитателя 40 разность К, - Ь поступает на преобразователь 46, осуществляющий преобразованием (К, - ь ), результат которого суммируется с результатом вычитателя 41 на суммато"ре 47. Если содержимое (Ь,) регистра6 не равно оо (1111), то выход элемента И-НЕ 36 равен "1", а если Ь ФК,т,е, выход вычитателя 40 не равен"0", то выход элемента ИЛИ 48 равен"1", и на дешифраторе 45 возбуждаетсячетвертый выход,Далее, если элемент 42 сравнениявыдает сигнал на первом выходе(Ь ФК, ), то ошибка произошла на -йпозиции 8=0, ,14):и элемент И 53открывается по сигналам с дешифратора 45 и элемента 42 сравнения.При совпадении номера позиции Э (выходы сумматора 47) и номера цикла сдешифратора 44 элемент 43 сравнениявыдает сигнал ца элемент И 53, открывая его и разрешая выдачу управляющих сигналов с генератора 50 управляющих импульсов на блок 9 исправления ошибки, а через элемент ИЛИ 491292189 10л лжимого Ко+К, в следующем цикле через четвертый ключ блока 10 на выход 14 устройства,Если ошибки не было, то дешифра тор 45 выдает сигнал на первом выходе и разрешает выдачу управляющих импульсов на первый ключ блока 10 для последовательной передачи информации с регистра 1 на выход 14 10 устройства. 9выдает сигнал на второй выход 60блока 11, открывая второй ключ блока 1 О,По сигналу Р 14 на регистр 26блока 9 переписываются сигналы с(73-76)-х разрядов регистра 1 (т,е.К,), имеющие ошибки, и в соответствии с формулой (13) на вычитателе28 из ошибочного символа К вычитается содержимое (д,) регистра 6.Полученный результат преобразуетсяв преобразователе 29 К -Ь,),складывается с Ь, на сумматоре 30 ипо сигналу15 записывается на реГистр 27 е 15В следующем цикле с помощью серии импульсов16 через второй ключблока 10 передается исправленный сим.вол на выход 14 устройства,На временной диаграмме (фиг. 5) 20показаны сигналы14 и 315 для 7 =ОАналогично происходит исправлениеФошибки на 15-й позиции 1 =2 -1. Приэтом=К , сигналы на выходах вычитателя 40 и элемента ИЛИ 48 равны"0", дешифратор 45 выдает сигнал натретьем выходе И, при наличии сигнала на втором выходе дешифратора 44элемент 52 И разрешает выдачу управляющих сигналов с генератора 50 на 30блок 9 исправления ошибки и в следующем цикле по второму выходу 60.блока 11 выдает сигнал на второй ключблока 10,Если ошибка произошла на 16-йпозиции (в принятом первом проверочном символе К ), то дешифратор 45выдает сигнал на четвертом выходе,так как Ь,оо и А ФК, но элемент42 сравнения выдает сигнал по второму выходу Ь =К, и при наличии сигнала на третьем выходе дешифратора44 элемент И 54 разрешает выдачу сигнала управления с генератора 50 управляющих импульсов на регистр 4для последовательной передачи егосодержимого в следующем цикле черезтретий ключ блока 10 на выход 14устройства,Если ошибка произошла на 17-й 50позиции (в принятом втором проверочном символе К, ), то дешифратор 45выдает сигнал на втором выходе,так как 1 сО и Ь ФК у и при наличии сигнала на четвертом выходе 55дешифратора 44, элемент И 51 разрешает выдачу сигнала управления сгенератора 50 на регистр 7 для последовательной передачи его содерУстройство декодирования с коррекцией ошибок позволяет декодировать кодовые слова, имеющие информационную часть, равную 2 ш-разрядных символов при двух ш-разрядных проверочных символах, имеющих один неисправный ш-разрядный символ, что позволяет без добавочной избыточности использовать это устройство в вычислительных машинах, имеющих, как правило, длину, слов, равную степени 2 (8, 16, 24, 32, 64 и т,д.), При этом применение степенных кодов позволяет избавиться от операций умножения и деления в поле СР(2 ), заменяя их операциями сложения и вычитания по модулю 2 -1 и преобразования кода, что позволяет упростить устройство, повьппая тем самым надежность его в работе и обеспечивая более удобную его микроминиатюризацию. Формула изобретения 1. Устройство для декодирования с коррекцией ошибок, содержащее входной регистр, информационный вход которого является информационным входом устройства, первые выходы подключены к соответствующим информационным входам первого формирователя проверочного символа, первый и второй буферные регистры, первые выходы первого буферного регистра подключены к соответствующим первым входам сумматорм,.и блок ключей, о т л ич а ю щ е е с я тем, что,с целью по. вьппения надежности функционирования, в него введены второй формирователь проверочного символа, . третий и четвертый буферные регистры, блок исправления ошибок и блок управления, первые информационные входы второго формирователя проверочного символа и первые входы блока управления под-ключены к соответствующим и первым выходам входного регистра, выходы первого формирователя проверочного15 20 25 30 40 45 50 55 символа соединены с соответствующими информационными входами первого и,третьего буферных регистров, выходы второго формирователя проверочного символа соединены с соответствующими информационными входами второго буферного регистра и вторыми входами блока управления, выходы третьего буферного регистра подключены к соответствующим первым информационным входам блока исправления ошибок и третьим входам блока управления, четвертые входы которого подключены к соответствующим первым выходам первого буферного регистра, пятый вход блока управления являет - ся тактовым входом устройства, выходы второго буферного регистра соединены с соответствующими вторыми входами сумматора, выходы которого подключены к соответствующим информационным входам четвертого буферного регистра,вторые выходы входного регистра соединены с соответствующими вторыми информационными входами блока исправления ошибок, третий выход входного регистра, выход блока исправления ошибок второй выход первого и выход четвертого буферных регистров подключены к соответствующим первым входам блока ключей, первый - четвертый выходы блока управления соединены с соответствующими вторыми входами блока ключей, выход которого является выходом устройства, пятые выходы блока управления подключены к соответствующим управляющим входам входного и буферных регистров, формирователей проверочного символа и блока исправления оши, бок.12. Устройство по и. 1, о т л ич а ю щ е е с я тем, что формирователь проверочного символа выполнен на буферных регистрах, вычитателе, сумматоре и преобразователе кода, информационные входы первого буферного регистра являются информационными входами формирователя, выходы первого буферного регистра подключены к соответствующим первым входам вычитателя и информационным входам второго буферного регистра, выходы которого соединены с соответствующими вторыми входами вычитателя, третий вход которого подключен к шине источника логической единицы, выходы вычитателя соединены с соответствующими первыми входами сумматора,вы. ходы преобразователя кода подключены к информационным входам третьегобуферного регистра, выходы которогосоединены с соответствующими вторымивходами сумматора, выходы которогоподключены к соответствующим информационным входам четвертого буферпого регистра, выходы которого соединены с соответствующими входами преобразователя кода и являются выходами формирователя, управляющие входы буферных регистров являются соответствуЮщими управляющими входами формирователя.3. Устройство по и, 1, о т л ич а ю щ е е с я тем, что блок исправления ошибок выполнен на буферных регистрах, вычитателе, преобразователе кода ц сумматоре, первые входы которого объединены с соответствующими первыми. входами вычитателя и являются соответствующими первыми информаццонньиц входами блока,информационные входы первого буферного регистра являются вторыми информационными входамц блока, выходы первого буферного регистра подключенык соответствующим вторым входам вычи-.тателя, выходы которого через преобразователь кода подключены к соответствующим вторым входам сумматора, выходы которого соединены с соответствующими информационнымц входами второго буферного регистра,выход которого является выходом блока, управляющие входы буферных регистров являются соответствующимивходами блока,4. Устройство по и. 1, о т л ич а ю щ е е с я тем, что блок управления выполнен на буферных регистрах, вычитателях, сумматоре, счетчике, генераторе управляющих импульсов, преобразователе кода, дешифраторах, элементах сравнения, элементах ИЛИ, элементах И ц элементах ИНЕ, входы первого элемента И-НЕ объединены с соответствующими входамцпервого буферного регистра ц являются первымц входами блока, выходыпервого буферного регистра подключены к соответствующим первым входампервого вычитателя, выходы которогосоединены со входамц первого элемента ИЛИ и через преобразователь кода - с соответствующими первымц входами сумматора, входы второго буферного регистра являются соответствующими вторыми входамц блока, выходывторого буферного регистра подключены к соответствующим вторым входампервого вычитателя, первым входампервого элемента сравнения и первымвходам второго вычитателя, вторыевходы которого объединены с соответствующими входами второго элемента И-НЕ и являются третьими входамиблока, вторые входы первого элементасравнения являются соответствующими 10четвертыми входами блока, вход счетчика объединен с первыми входами эле,ментов И и является пятым входомблока, выходы счетчика подключены ксоответствующим входам первого дешифратора, первые выходы которогосоединены с соответствующими первымивходами генератора управляющих им 1пульсов и второго элемента сравнения,выходы второго вычитателя подключены 20к соответствующим вторым входам сумматора, выходы которого соединены ссоответствующими вторыми входами второго элемента сравнения, выход первого элемента ИЛИ соединен с первымвходом второго дешифратора, выходыпервого и второго элементов И-НЕ подключены к вторым входам соответственно генератора управляющих импульсови второго дешифратора, первый выход 30 которого является первым выходомблока, второй и третий выходы второгодешифратора подключены к вторым входам соответственно первого и второго элементов И четвертый выходвторого дешифратора соединен с вторыми входами третьего и четвертогоэлементов И, выходы второго и третьего элементов И подключены к входамвторого элемента ИЛИ, выход которогоявляется вторым выходом блока, второй, третий и четвертый выходы первого дешифратора подключены к третьим входам соответственно второго,четвертого и первого элементов И, выход второго элемента сравнения соединен с третьим входом третьего элемента И, первый и второй выходы первого элемента сравнения соединены счетвертыми входами соответственнотретьего и четвертого элементов И,выходы четвертого и первого элементов И являются соответственно третьим и четвертым выходами блока, выходы элемента И с первого по четвертый подключены к соответствуюшимтретьим входам генератора управляющих импульсов, выходы которогоявляются пятыми выходами бло -1ка,1292189 0 цикл цикл Ецйч 79 цио Брам 7 бцикл 77 щси Йщкл цикл Рси77 Г 8 0 Ч 5 Юб 7 Ябб ббЮ 70 9 5 8 7 оставитель О,Р Техред И.Попов дактор А,Козо 902 Подписноственного комитета СССРретений и открытийН, Раушская наб., д, 4 Тираж ЗНИИПИ Госуда по делам изо 13035, Москва