Декодер линейного кода

(54) ДЕКОДЕР ЛИНГ (57) Изобретение электронике и мож но в цифровом рад изобретения - пов чивости путем обн кратности С + 1 и относится к радио ет быть использов ионещании. Цельппение помехоустой техниче ужения выше. Держит буфе гебраическая- М.: Мир, 1971 2 по ромо лок 5 па авления,шибок многочлена, схем,п. ф-лы, 4 ил. исления степе сравнен ГОСУДАРСТВЕННЫЙ НОМИТЕТ СССР ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТ ПИСАНИЕ ИЗОБР КОМУ СВИДЕТЕЛЬСТВ(46) 23.10,88. Бил. У 39171) Ленинградский электрокий институт связиим. проф. М.А.Бонч-Бруевича172) З,А.Бесперстов(56) Берлекэмп Э, Алтеория кодирования.с. 145,неиного кода сод гистр 1, суммато вычислитель 3 си ческий блок 4, члена, блок 6 уп кировки, счетчик ошибок кодер ли рный реулю два, рифметияти много- блок 7 масблок 9 выИзобретение Относится к радиоэлектронике и может быть использовано в цифровом. радиовещании.Целью изобретения является повышение помехоустойчивости путем обнаружения ошибок кратности С+1 и выше.На фиг.1 приведена структурнаясхема предлагаемого декодера; наФиг. 2 - 4 - схемы возможных реализа- Оций блока маскировки, блока вычисления степени многочлена и блока управления соответственно,Декодер линейного кода (Фиг.1) со держит буферный регистр 1, сумматор,2 по модулю два, вычислитель 3 синд,ромов, арифметический блок 4, блок 5памяти многочлена, блок 6 управления;блок 7 маскировки, счетчик Я ошибок,блок 9 вычисления степени многочлена и блок 10 сравнения.Блок 7 маскировки (фиг.2) содержитбуферные регистры 11 и 12, триггер13 и элементы 2 ИШИ 14 и 15.Блок 9 вычисления степени многочлена (Фиг.З) содержит элементы И16.1-16,Б и 17,1-17,(И), дешифратор 18 и триггеры 19.1-19.И.Блок 6 управления (фиг.4) содержитсчетчик 20 и блок 21 памяти. ЗОДекодер линейного кода работаетследующим образом.Принимаемая л-разрядная комбинацияпоступает в накопитель и одновременно в вычислитель синдромов, где вычисляют синдромы принимаемой комбинации. Как только принимаемая комбинация оказывается полностью записаннойв буферном регистре 1, в вычислителе 3 синдромов оканчивается вычисле"ние синдромов,и вычисленные синдромыпереписываются по сигналу с блока 6управления в арифметический блок 4,где по ним вычисляетея многочлен ошибок б (Е), степень которого равна Сили меньше в зависимости от кратности ошибок, Коэффициенты многочлена8(Е) принадлежат полю СР(2 ), гдеш = 1 оя и. Всего может быть 2 разв 1личных многочленов (р(Е), С другойстороны, всего может быть 2 " " различных синдромов и, следовательно,2 " различных смежных классов,Приэтом шС = и - К.Каждому смежному классу можно пос"тавить в однозначное соответствиеодин многочлен. Многочлены б (Е),соответствующие исправляемым данным кодом ошибкам, называются допустимыми,остальные - недопустимыми. Все многочлены первой степени соответствуютоднократной ошибке и, следовательно,являются допустимыми. Но не все многочлены б(Е) степени 2 и выше являются допустимыми многочленами, таккак С2 , где с С, а С - равночислу -кратных ошибок.Если в принятой комбинации имеетсяС ошибочных сигналов, то степень многочлена б (Е) равна . Иногочлен б (Е) в данном случае имеетразличных корней, принадлежащих полюОР(.2 ). Если в принятой комбинацииимеется х ) С ошибочных символов, тостепень многочлена б (Е) меньше илиравна С, Число корней многочленавсегда равно степени многочлена, Нов данном случае не все корни многочлена 5 (Е) принадлежат полю ГР(2 ),некоторые или все корни многочленапринадлежат к некоторому расширениюполя СР(2 ).Иэ арифметического блока 4 многочлен ошибок б (Е) переписывается вблок 5 памяти, где в него поочередно подставляются элементы поля, приэтом нз буферного регистра 1 считывается декодируемая комбинация. Каждому считываемому из накопителя символу соответствует подставляемый. ввмногочлен ошибок элемент поля СГ(2 ).Если при подстановке очередного элемента поля.многочлен ошибок обращается в ноль, то выводимый в данныймомент из буферного регистрасимвол ошибочен, С блока 5 на вход сумматора 2 по модулю два поступаетединица, которая в сумматоре 2 помодулю два складывается с символом,поступающим с буферного регистра .Тем самым данный символ кодовой комбинации инвертируется, т,е. происходит исправление ошибки, Число единиц,т;е. число исправляемых ошибок в кодовой комбинации, поступающих с блока5 за время декодирования одной кодовой комбинации, подсчитывается всчетчике 8 ошибок,Предположим, что в блок 5 записан недопустимый многочлен. В этом случае может оказаться, что ни один из элементов поля 07(2) не является корнем данного многочлена, или корней, принадлежащих полю ОГ(2 ),меньше степени многочлена ошибок. В этом случае оказывается, что с выхода бло 1432786ка 5 на вход счетчика 8 ошибок и сумматора 2 по модулю два поступает меньше единиц, чем степеньмногочлена б (Х) . Степень мцогочлена Я (Е) подсчитывается в блоке 9 вычисления степени многочлена ошибок, куда из арифметического блока 4 записывается многочлен ошибок,В конце цикла декодирования кодо О вой комбинации в блоке 1 О сравнения сравниваются показания счетчика Р ошибок и блока 9 вычисления степенимногочлена,Если показания совпадают, то на 15блок 7 маскировки с блока 1 О сравнения поступает сигнал "О". По этомусигналу декодирования н данный момент кодовая комбинация с блока 7 маскировки поступает на выход устройст Она. Кроме того, эта комбинация запоминается в блоке 7 маскировки.Если показания счетчика 8 ошибокменьше показания блока 9 вычислениястепени многочлеца, то с блока 10 25сравнения на вход блока 7 маскировки поступает сигнал "1". По этому сигналу в блоке 7 маскировки декодиронанная в данный момент кодовая комбинация стирается, так как н ней об Онаружена неисправная комбинация ошибок, На выход устройства поступаетпредыдущая правильно декодированная.кодовая комбинация, которая хранилась до этого в блоке 7 маскировкиБлок 7 маскировки работает следующим образом.:С выхода сумматора 2 по модулюдва на вход первого буферного регистра 11 поступает декодируемая комби Онация, при этом из него выводится предыдущая декодированная комбинация,которая поступает на первые информационные входы элементов 2 И-ИЛИ 14 и 15,Как только последний символ комбинации оказывается записанным н первыйбуферный регистр 11, с блока 10 сравнения на триггер .13 поступает сигнал"0", если в кодовой комбинации нетошибок, произошли исправимые ошибки,или сигнал "1", если в этой кодовойкомбинации обнаружена неисправимаякомбинация ошибок,Если с блока 10 сравнения пришел.сигнал "О", то триггер 13 остаетсяв исходном состоянии и сигнал с егоинверсного выхода разрешает выдачукомбинации на выход устройства и запись этой комбинации во второй буФерцый регистр 2, а сигнал с прямоговыхода запрещает выдачу комбинациица выход устройства с второго буферного регистра 12 и перезапись этойкомбинации н регистр.Если с блока 10 сравнения пришелсигнал "1", то триггер 13 перебрасывается в состояние, когда на его прямом выходе присутствует сигнал логической "1". По сигналу с прямого выхода триггера 13 разрешаются выдачакомбинации с второго буферного регистра 12 ца выход устройства и перезапись выдаваемой комбинации в регистр.По сигналу с инверсного выхода запреп 1 аются выдача ца выход устройствакомбинации с первого буферного регистра 11 и перезапись этой комбинациино второй буферный регистр 12, Темсамым ца выход устройства поступаетне декодцронаццая н данный момент кодовая комбинация (н ней обнаруженанеисправимая комбинация ошибок), апредыдущая декодировацная без ошибокили с исправляемой ошибкой кодоваякомбинация.Блок 9 вычисления степени многочлена работает следующим образом.Из арифметического блока 4 на входблока 9 последовательно поступают вычисленные козффициенты многочленаошибок, Если степень многочлена равна 1, т.е. коэффициент Б многочлена ошибок не ранец нулю, то срабатывает триггер 19,11 Т. Сигнал логической "1" с его прямого выхода поступает на дешифратор 1 8. Сигнал синверсного выхода этого триггера поступает на элементы И 17, запрещаятем самым срабатывание триггеров19 е 1-19.(И) Т в,Т. С прямьп(выходов этих триггеров на дешифратор 18 поступает сигнал логического"0. На выходах дешифратора присутствует сигнал, соответствующий двоичному числуЕсли коэффициент б = О, то сигнал с инверсного выхода триггера19.И Т разрешает срабатывание триггеров 19.1-19,(И) ТТ, в зависимости от того, равны или неранцы нулю коэффициенты б ееб еБлок 6 управления работает следующим образом,Состояние счетчика 20 в карый момент времени является адресом для блока 21 памяти. В блоке 21 памяти хранятся М-разрядные двоичные комбина1432786 6метического блока являются первым,вторым и третьим входами декодера соответственно, о т л и ч а ю щ и й с ятем, что, с целью повышения помехо 5устойчивости декодера, в него введены блок маскировки, счетчик ошибок,блок сравнения, блок вычисления сте"пени многочлена и блок управления,1 О вход которого соединен с вторым входом декодера, первый, второй, третий,четвертый и пятый выходы - с третьими.входами вычислителя синдромов и арифметического блока, первыми вхо 16 дами блока вычисления степени многочлена и блока сравнения и объединенными первымивходами счетчика ошибок и блока .маскировки соответственно, второй вход20 счетчика ошибок соединен с выходомблока памяти многочлена, выход - свторым входом .блока сравнения, второй вход блока вычисления степенимногочлена соединен с выходом арифб метического блока, выход - с третьимвходом блока сравнения, выход которого соединен с вторым входом блокамаскировки, третий и четвертый входыкоторого соединены соответственно сЗО вторым входом декодера и выходомсумматора по модулю два, выход блокамаскировки является выходом декоде- раф ции, где М - число устройств, которыми нужно управлять, Выход каждогоразряда блока 21 памяти соединен свходом того устройства, работой которого управляет данный разряд блока21 памяти.Например, на вход вычислителя 3синдромов с блока 6 управления должен поступать только один сигнал,указывающий, в какой момент регистрьвычислителя 3 синдромов обнуляются.Поэтому вычислитель 3 синдромов связан только с одним разрядом блока 21памяти блока 6 управления. С выходаэтого разряда на вход вычислителя 3синдромов в течение итактов поступают нули, а на и-м такте - единицытак как на п-м такте заканчиваетсявычисление синдромов, и после того,как эти синдромы будут записаны варифметический блок 4, регистры вычислителя синдромов должны быть обнулены.Арифметический блок 4 значительно более сложное устройство, чем вычислитель 3 синдромов, и для его работы требуется больше управляющихсигналов. Число управляющих сигналовзависит от конкретной реализацииарифметического блока 4,Блок 10 сравнения, блок 7 маски,ровки и счетчик 8 ошибок для своейработы требуют также по одному управЛяющему сигналу, поэтому их управляющие входы соединены с соответствующими разрядами блока 21 памяти блока 6,управления,. Блок вычисления степени многочле на в зависимости от конкретной реализации может потребовать нескольких управляющих сигналов. Формула изобретения 45 1. Декодер линейного кода, содержащий последовательно соединенные буферный регистр и сумматор по модулю два и последовательно соединенные 5 О вычислитель синдромов, арифметический блок и блок памяти многочленов, выход которого соединен с вторым входом сумматора по модулю два, первые объединенные входы буферного регист ра и вычислителя синдромов, вторые объединенные входы буферного регистра, вычислителя синдромов и блока памяти многочленов и второй вход ариф 2. Декодер по п.1, о т л и ч а ю - щ и й с я тем, что блок управления содержит последовательно соединенные счетчик и блок памяти, вход счетчика является входом устройства, выходы блока памяти - соответствующими выходами устройства.3. Декодер по и.1, о т л и ч а ищ и й с я тем, что, блок маскировки содержит триггер, элементы 2 И-ИЛИ, регистры, первый и второй входы триггера являются соответственно первым и вторым входами блока маскировки, объединенные первые входы регистров являются третьим входом блока маскировки, второй вход первого регистра является четвертым входом блока маскировки, выход первого регистра подключен к первым входам элементов 2 И-ИЛИ, выход первого элемента 2 И-ИЛИ соединен с вторым входом второго регистра, выход которого соединен с вторыми входами элементов 2 И-ИЛИ,прямой и инверсный выходы триггера соединены соответственно с третьими ичетвертыми входами элементов 2 И-ИЛИ,выход второго элемента 2 И-ИЛИ является выходом блока маскировки. 54. Декодер по п.1, о т л и ч а ющ и й с я тем, что блок вычисления степени многочлена содержит группы элементов И, И триггеров, где Л - степень многочлена ошибок, и дешифратор, первые входы элементов И первой группы и объединенные первые входы триггеров являются соответствующими первыми входами блока вычисления степени многочлена, выходы пер вых элементов И первой группы, кроме последнего, соединены с первыми вхо" дами соответствующих элементов И второй группы, выходы которых соединены с вторыми входами соответствующих триггеров, кроме последнего, выход последнего элемента И первойгруппы соединен с вторым входом последнего триггера, инверсные выходытриггера, кроме первого, соединеныс соответствующими входами 1-(-1)( = 2И) элементов И второй группы, вторые инверсные входы элементовИ первой группы соответственно объединены и являются вторыми входамиблока вычисления степени многочлена,прямые выходы триггеров соединены ссоответствующими входами дешифратора,выходы которого являются выходамиблока.1432786 Составитель С Техред И.Вере ер ес тевич Обручар Коррек актор О,Мрковецкая аз 546 29 длисное Производственно-полиграфическое предприятие, г. Ужгород, ул. Проектная, 4 4/55 Тир ВНИИПИ Государственног по делам изобретений 113035, Москва, Ж, Рауш