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

 

Изобретение относится к радиоэлектронике и может быть использовано в цифровом радиовещании. Цель изобретения - ловышение помехоустойчивости путем обнаружения ошибок кратности t + 1 и выше. Декодер линейного кода содержит буферньтй регистр 1, сумматор 2 по модулю два, вычислитель 3 синдромов, арифметический блок 4, блок 5 памяти многочлена , блок 6 управления, блок 7 маскировки , счетчик 8 ошибок, блок 9 вычисления степени многочлена, схему 10 сравнения. 3 з.п. ф-лы, 4 ил. с «

СОЮЗ СОВЕТСНИХ

С00ИАЛИСТИЧЕСНИХ

РЕСПУБЛИН

ОПИСАНИЕ ИЗОБРЕЛ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

Фиг.1

ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ (21) 4170332/24-24 (22) 30,12 ° 86 (46) 23.10,88. Бил, У 39 (71) Ленинградский электротехнический институт связи им. проф. М.А.Бонч-Бруевича (72) 3.А.Бесперстов (53) 6?1.398 (088,8) (56) Берлекэмп 3. Алгебраическая теория кодирования, — M.: Мир, 1971, с. 145, „„SU„„3 432786 А1 (54) ДЕКОДЕР ЛИНЕЙНОГО K0TfA (57) Изобретение относится к радиоэлектронике и может быть использовано в цифровом радиовещании. Цель изобретения — повышение помехоустойчивости путем обнаружения ошибок кратности t + 1 и выше. Декодер линейного кода содержит буферный регистр l сумматор 2 по модулю два, . вычислитель 3 синдромов, арифметический блок 4, блок 5 памяти многочлена, блок 6 управления, блок 7 маскировки, счетчик 8 ошибок, блок 9 вычисления степени многочлена, схему

10 сравнения, 3 з,п. ф-лы, 4 ил.

1432786

Изобретение относится к радиоэлектронике и может быть использова но в цифровом. радиовещании.

Целью изобретения является повышение помехоустойчивости путем обнаружения ошибок кратности С+1 и выше.

На фиг.l приведена структурная схема предлагаемого декодера; на фиг. 2 — 4 — схемы возможных реализа- !и ций блока маскировки, блока вычисления степени многочлена и блока управления соответственно.

Декодер линейного кода (фиг.l) со держит буферный регистр 1, сумматор

,2 по модулю два, вычислитель 3 синд; ромов, арифметический блок 4, блок 5 .памяти многочлена, блок 6 управления; блок 7 маскировки, счетчик 8 ошибок, блок 9 вычисления степени многочлена и блок 10 сравнения.

Блок 7 маскировки (фиг.2) содержит буферные регистры 11 и 12, триггер

13 и элементы 2И-К1Н 14 и 15.

Блок 9 вычисления степени много- 25 члена (фиг.З) содержит элементы И

16.1-16.И и 17.1-17,(N-I), дешифратор 18 и триггеры 19.1-19.N.

Блок 6 управления (фиг.4) содержит счетчик ?О и блок 21 памяти. 30

Декодер линейного кода работает .следующим образом.

Принимаемая л-разрядная комбинация ! .поступает в накопитель и одновремен .но в вычислитель синдромов, где вычисляют синдромы принимаемой комбинации. Как только принимаемая комбинация оказывается полностью записанной в буферном регистре 1, в вычислителе 3 синдромов оканчивается вычисле" ние синдромов .и вычисленные синдромы переписываются по сигналу с блока 6 управления в арифметический блок 4, где по ним вычисляетея многочлен ошибок б (7,), степень которого равна t или меньше в зависимости от кратности ошибок. Коэффициенты многочлена

G(7,) принадлежат полю СР(2 ), где

m = lop;

Каждому смежному классу можно пос"55 тавить в однозначное соответствие один многочлен. Многочлены б (Z),ñîответствующие исправляемым данным кодом ошибкам, называются допустимыми, остальные — недопустимыми. Все многочлены первой степени соответствуют однократной ошибке и, следовательно, являются допустимыми. Но не все многочлены 6 (7,) степени 2 и выше являются допустимыми многочленами, так как С„ ?, где i а С, а С„ — равно числу i-кратных ошибок.

Если в принятой комбинации имеется i С ошибочных сигналов, то степень многочлена 0 (7) равна i. Многочлен 5 (Z) в данном случае имеет различных корней, принадлежащих полю

GF(.2 ). Если в принятой комбинации имеется i > t ошибочных символов, то степень многочлена б (7) меньше или равна t. Число корней многочлена всегда равно степени многочлена. Но в данном случае не все корни многочлена 5 (Z) принадлежат полю C!F(2 ), некоторые или все корни многочлена принадлежат к некоторому расширению поля aF(2 ).

Иэ арифметического блока 4 многочлен ошибок б (7,) переписывается в блок 5 памяти, где в него поочередно подставляются элементы поля, при этом нз буферного регистра 1 считывается декодируемая комбинация. Каждому считываемому из накопителя символу соответствует подставляемый. в

tl1 многочлен ошибок элемент поля GF(2 ).

Если при подстановке очередного элемента поля.многочлен ошибок обрашается в ноль, то выводимый в данный момент из буферного регистра символ ошибочен, С блока 5 на вход сумматора 2 по модулю два поступает единица, которая в сумматоре 2 по модулю два складывается с символом, поступающим с буферного регистра !.

Тем самым данный символ кодовой комбинации инвертируется, т,е. происходит исправление ошибки, Число единиц, т;е. число исправляемых ошибок в кодовой комбинации, поступающих с блока

5 за время декодирования одной кодовой комбинации, подсчитывается в счетчике 8 ошибок, Предположим, что в блок 5 записан недопустимый многочлен. В этом случае может оказаться, что ни один из элементов поля 07(2 ) не является корнем данного многочлена, или корней, принадлежащих полю 0Г(2 ),меньше степени многочлена ошибок. В этом случае оказывается, что с выхода бло1432786 ка 5 на вход счетчика 8 ошибок и сумматора 2 по модулю два поступает меньше единиц, чем степень многочле на 6 (7,) . Степень многочлена G (Е) подсчитывается в блоке 9 вычисления степени многочлена ошибок, куда из арифметического блока 4 записывается многочлен ошибок, В конце цикла декодирования кодо- 1О вой комбинации в блоке 10 сравнения сравниваются показания счетчика Р ошибок и блока 9 вычисления степени

55 многочлена, Если показания совпадают, то на 15 блок 7 маскировки с блока 10 сравнения поступает сигнал "0". IIo этому сигналу декодирования в данный момент кодовая комбинация с блока 7 маскировки поступает на выход устройст-- 2О на. Кроме того, эта комбинация запоминается в блоке 7 маскировки.

Если показания счетчика 8 ошибок меньше показания блока 9 вычисления степени многочлена, то с блока 10 25 сравнения на вход блока 7 маскировки поступает сигнал "1". По этому сигналу в блоке 7 маскировки декодированная в данный момент кодовая комбинация стирается, так как в ней об- 30 наружена неисправная комбинация ошибок, На выход устройства поступает предыдущая правильно декодированная. кодовая комбинация, которая хранилась до этого в блоке 7 маскировки.

Блок 7 маскировки работает следующим образом.

:С выхода сумматора 2 по модулю два на вход первого буферного регистра ll поступает декодируемая комби- 4О нация, при этом из него выводится предыдущая декодированная комбинация,которая поступает на первые информационные входы элементов 2И-HJIH 14 и 15, Как только последний символ комбина- 45 ции оказывается записанным в первый буферный регистр 11, с блока 10 сравнения на триггер .13 поступает сигнал

"0", если в кодовой комбинации нет ошибок, произошли исправимые ошибки, или сигнал "1", если в этой кодовой комбинации обнаруяена неисправимая комбинация ошибок.

Если с блока 10 сравнения пришел сигнал "0", то триггер 13 остается в исходном состоянии и сигнал с его инверсного выхода разрешает выдачу комбинации на выход устройства и запись этой комбинации во второй буферный регистр !2, а сигнал с прямого выхода запрещает выдачу комбинации на выход устройства с второго буферного регистра 12 и перезапись этой комбинации в регистр.

Fñëè с блока 10 сравнения пришел сигнал "1", то триггер 13 перебрасывается в состояние, когда на его прямом выходе присутствует сигнал логической "1". По сигналу с прямого выхода триггера 13 разрешаются выдача комбинации с второго буферного регистра 12 на выход устройства и перезапись выдаваемой комбинации в регистр.

По сигналу с инверсного выхода запрещаются выдача на выход устройства комбинации с первого буферного регистра 11 и перезапись этой комбинации во второй буферный регистр 12. Тем самым на выход устройства поступает не декодиронанная в данный момент кодовая комбинация (в ней обнаружена неисправимая комбинация ошибок), а предыдущая декодированная без ошибок или с исправляемой ошибкой кодовая комбинация, Блок 9 вычисления степени многочлена работает следующим образом.

Из арифметического блока 4 на вход блока 9 последовательно поступают вычислениые коэффициенты многочлена ошибок. Если степень многочлена равна t, т.е. коэффициент G< многочлена ошибок не равен нулю, то срабатывает триггер 19,NTt. Сигнал логической "1" с его прямого выхода поступает на дешифратор 1 8. Сигнал с инверcíoão выхода этого триггера поступает на элементы И 17, запрещая тем самым срабатывание триггеров

19.1-19.(N-1) Т„,...,T, . С прямых выходов этих триггеров на дешифратор 18 поступает сигнал логического 0 . На выходах дешифратора присутствует сигнал, соответствующий двоичному числу t, Если коэффициент G< = О, то сигнал с инверсного выхода триггера

19.N Т р-зрешает срабатывание триггеров 19.1 — 19,(И-1) Т,,...,Т, в зависимости от того, равны или не равны нулю коэффициенты 6,,...Д .

Блок 6 управления работает следующим образом.

Состояние счетчика 20 в карый момент времени является адресом для блока 21 памяти. В блоке 21 памяти хранятся M-разрядные двоичные комбина1432786 6 метического блока являются первым, вторым и третьим входами декодера соответственно, о т.л и ч а ю шийся тем, что, с целью повышения помехо5 устойчивости декодера, в него введены блок маскировки, счетчик ошибок, блок сравнения, блок вычисления степени многочлена и блок управления, 1g вход которого соединен с вторым входом декодера, первый, второй, третий, четвертый и пятый выходы — с третьими входами вычислителя синдромов и арифметического блока, первыми вхо15 дами блока вычисления степени многочлена и блока сравнения и объединенными первыми входами счетчика ошибок и блока маскировки соответственно, второй вход

20 счетчика ошибок соединен с выходом блока памяти многочлена, выход — с вторым входом .блока сравнения, второй вход блока вычисления степени многочлена соединен с выходом ариф метического блока, выход — c третьим входом блока сравнения, выход которого соединен с вторым входом блока маскировки, третий и четвертый входы которого соединены соответственно с

ЗО вторым входом декодера и выходом сумматора по модулю два, выход блока маскировки является выходом декодера ° ции, где М вЂ” число устройств, которы ми нужно управлять, Выход каждого разряда блока 21 памяти соединен с входом того устройства, работой кото рого управляет данный разряд блока

21 памяти.

Например, на вход вычислителя 3 синдромов с блока 6 управления должен поступать только один сигнал, указывающий, в какой момент регистрь вычислителя 3 синдромов обнуляются. ,Поэтому вычислитель 3 синдромов связан только с одним разрядом блока 21 памяти блока 6 управления. С выходя этого разряда на вход вычислителя 3 синдромов s течение и-1 тактов посту лают нули, а на и-м такте — единицы так как íà и-м такте заканчивается вычисление синдромов, и после того, как эти синдромы будут записаны в арифметический блок 4, регистры вычислителя синдромов должны быть обнулены.

Арифметический блок 4 значительно более сложное устройство, чем вычислитель 3 синдромов, и для его работы требуется больше управляющих сигналов. Число управляющих сигналов зависит от конкретной реализации арифметического блока 4, Блок 10 сравнения, блок 7 маски, ровки и счетчик 8 ошибок для своей работы требуют также по одному управЛяющему сигналу, поэтому их управляю- 35 щие входы соединены с соответствующими разрядами блока 21 памяти блока 6 ,управления..

Блок вычисления степени многочле- 4р на в зависимости от конкретной реализации может потребовать нескольких управляющих сигналов.

Формула изобретения 4r„

I Декодер линейного кода, содержащий последовательно соединенные буферный регистр и сумматор по модулю два и последовательно соединенные бб вычислитель синдромов, арифметический блок и блок памяти многочленов, выход которого соединен с вторым входом сумматора по модулю два, первые объединенные входы буферного регист- 55 ра и вычислителя синдромов, вторые объединенные входы буферного регистра, вычислителя синдромов и блока памяти многочленов и второй вход ариф?. Декодер по п.1, о т л и ч а юшийся тем, что блок управления содержит последовательно соединенные счетчик и блок памяти, вход счетчика является входом устройства, выходы блока памяти — соответствующими выходами устройства.

3. Декодер по п.1, о т л и ч а ишийся тем, что, блок маскировки содержит триггер, элементы 2И-ИЛИ, регистры, первый и второй входы триггера являются соответственно первым и вторым входами блока маскировки, объединенные первые входы регистров являются третьим входом блока маскировки, второй вход первого регистра является четвертым входом блока маскировКи, выход первого регистра подключен к первым входам элементов

2И-ИЛИ, выход первого элемента 2И-ИЛИ соединен с вторым входом второго регистра, выход которого соединен с вторыми входами элементов 2И-ИЛИ,прямой и инверсный выходы триггера соединены соответственно с третьими и

1432786 четвертыми входами элементов 2И-ИЛИ, выход второго элемента 2И-ИЛИ является выходом блока маскировки.

4. Декодер по п.1, о т л и ч а юшийся тем, что блок вычисления степени многочлена содержит группы элементов И, N триггеров,,где N— степень многочлена ошибок, и дешифратор, первые входы элементов И первой группы и объединенные первые входы триггеров являются соответствующими первыми входами блока вычисления степени многочлена, выходы пер- 15 вых элементов И первой группы, кроме последнего, соединены с первыми входами соответствующих элементов И второй группы, выходы которых соединены с вторыми входами соответствующих триггеров, кроме последнего, выход последнего элемента И первой группы соединен с вторым входом последнего триггера, инверсные выходы триггера, кроме первого, соединены с соответствующими входами 1-(i-1) (i = 2,...,N) элементов И второй группы, вторые инверсные входы элементов

И первой группы соответственно объединены и являются вторыми входами блока вычисления степени многочлена, прямые выходы триггеров соединены с соответствующими входами дешифратора, выходы которого являются выходами блока.

1432786 /г 9f

РигЗ

Составитель С. Берестевич

Техред И.Верес

Корректор A.06ðó÷ ð

Редактор О.Мрковецкая

Заказ 5464/55 Тираж 929

ВНИИПИ Государственного комитета СССР по делам изобретений и открытий.

113035, Москва, Ж-35, Раушская наб., д. 4/5

Подписное

Производственно-полиграфическое предприятие, г. Ужгород, ул. Проектная, 4