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

 

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

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИН (19> 0 (и) (5D 4 Н 03 М 13/00

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ

4»,, (ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 4179584/24-24 (22) 12. 01.87 (46) 07.10.88. Бюл. й" 37 (72) Я.А. Качерович (53) 621.391.256 (088.8) (56) Качерович Я.А. Декодирование циклических кодов модифицированным методом вылавливания ошибок. Труды

НИИРадио, 1981, У 2, с. 48-50. (54) УСТРОЙСТВО ДЛЯ ДЕКОДИРОВАНИЯ

ЦИКЛИЧЕСКИХ КОДОВ

{57) Изобретение относится к передаче дискретной информации по каналам связи и может быть использовано в системах передачи сигналов на фоне помех, в частности в системах телеупрарле- . ния и телеконтроля радиовещательного оборудования. Цель изобретения — повьппение надежности путем упрощения

1429325

24 RS /S

Ц ю П л °

R1+R3 К4+К5/S л. схемы устройства, Устройство реализу:ет модифицированный метод выпавлива;ния ошибок, применимый в тех случаях, когда по меньшей мере при одном из циклических сдвигов кодового слова на информационные разряды попадает не более одного искаженного кодового символа. Этот метод применим ко всем ф клическим кодам длины n «» 45, а также к многим более длинным кодаи. ,Декодирование производится за n(k+1) Изобретение относится к передаче дискретной информации по каналам свя зи и может быть использовано в системах передачи сигналов на Фоне помех, в частности в системах телеуправления и телеконтроля радиовещательного обо рудования.

Целью изобретения является повьппение надежности путем упрощения схемы устройства, Устройство реализует известный модифицированный метод вылавливания ошибок, применимый ко всем коротким циклическим кодаи длины п «» 45, а так15 же ко многим более длинным кодам.

На фиг. 1 изображена функциональная схема предлагаемого устройства, на фиг. 2 — схема порогового элемен-

T8. ° 20

Устройство (фиг. 1) содержит иразрядный буферныйрегистр 1, генератор 2 синдрома, .RS-триггер 3,. генератор 4(n-Е)-разрядного кода, где — число информационных разрядов кода, распределитель 5 импульсов, элементы ИСКЛЮЧАЮЩЕЕ ИЛИ б «бр » пороговый элемент 7, группу элементов

И 8, -8 „, элемент И 8„,< и генератор

9 импульсов. 30

Пороговый элемент (фиг. 2) содер- . жит триггер 10, .ограничительные элементы 11 и 12, компаратор 13 и две группы согласующих элементов 14.114.2 и 15 1-15, (n-К). 35

Резисторы первого 14.1 и второго

14.2 согласующих элементов 6 первой группы имеют номинальную величину сопротивления R1 и R2 соответственно, шагов работы устройства (где n kсоответственно длина кода и число информационных символов). Устройство состоит из буферного регистра 1, генератора синдрома 2, триггера 3, ге,нератора 4 п-k,-разрядного кода, распределителя 5 импульсов,элементов ИСКЛЮЧАЮЩЕЕ ИЛИ 6 -6„», порогового элемента 7, группы элементов И 8,-8» элемента И 8 „„, и генератора 9 импульсов. 1 з.п. Ф-лы, 2 ил. резисторы первого 11 и второго 12 ограничительных элементов — R3 и R4, резисторы согласующих элементов второй группы - R5.

В исходный момент триггер 1 О находится в состоянии "О", при этом на первом выходе триггера потенциал

О, на втором выходе потенциал +U на первом входе компаратора потенциЩ ал U - — — (внутренним сопротивлениИ+И ем отпертых диодов пренебрегаем). Если на S из (и-k) сигнальных входовсигнал "1", а на остальных — сигнал

"0", то открыты S соответствующих диодов, включенных последовательно с резисторами 15.1-15.(п-k) а остальные (и-k-S) диодов заперты, При этом потенциал на втором входе компаКу/S ратора равен U †- - -. Компаратор

R4+R5/S выдает на выходе сигнал " 1" в том случае, если сигнал на его первом входе меньше, чем сигнал на втором входе, и выдает сигнал "0" в противном случае, Величины R1 и R3 выбираются такими, чтобы

Для переключения порога сигнал "1" подается на S-вход триггера, переводя его в состояние "1". В результате потенциал на первом входе компаратора становится равным U ††-. Пос,R<

R2+R3 кольку порог должен быть переключен

14293 со значения t на значение (t-E), то

R2 нахоДится из условия U — ——

R1

R5(t-1)

R2+R3

Ц

R4+R5/(t-E) 5

Устройство реализует известный модифицированный метод вылавливания ошибок. Этот метод можно применять в тех случаях, когда по меньшей мере

1 10 при одном из циклических сдвигов кодового слова на информационные разряды попадает не более одного искаженного кодов ог о символа .

Принимаемая и-символьная кодовая комбинация записываетсяиз каналав буГ ферный регистр 1. После этого на вход тактовых импульсов подаются и тактовых импульсов. Каждый такой импульс осуществляет циклический сдвиг 20 на один разряд содержимого буферного регистра и генератора 2 синдрома, В последнем в соответствии с известным устройством каждый раз образуется синдром, соответствующий сдвинутому кодовому слову. Каждый тактовый импульс переводит также триггер 3 в состояние "1". При этом открывается элемент 8„, и импульсы от генератора 9 проходят через него, попадая на вход сдвига генератора 4(n-k)разрядного кода и вход распределителя 5 импульсов. В начальный момент генератор 4 находится в состоянии

"0", а со всех его выходов снимается сигнал "0". Также и на всех выходах распределителя 5 импульсов в начальный момент — сигнал "0".

Если вектор синдрома, записанный в генераторе 2 синдрома, имеет вес, не превышающий t то ошибки содержатся только в первых (п-k) разрядах кодовой комбинации (проверочных разрядах) и могут быть исправлены путем поразрядного прибавления вектора 4> синдрома к первым (n-k) разрядам кодовой комбинации. Таким образом, после прихода тактового импульса на выходах элементов ИСКЛЮЧАЮЩЕЕ ИЛИ 6 — б „ „ оказывается вектор синдрома.

Подключенный к этим выходам пороговый элемент 7 фиксирует, что превышает ли вес двоичного вектора на его входах величину t. Если превышает, то на выходе порогового элемента— сигнал "0", в противном случае — сигнал "1". Если ошибочные символы имеются только в проверочных разрядах, то после прихода тактового импульса

»а выходе порогового элемента 7 возникает сигнал "1". Этот сигнал проходит через те из элементов И 8,-8„, на первые входы которых подается сигнал "1" с выходов элементов ИСКЛЮЧАЮЩЕЕ ИЛИ, а именно через те из соответствующих проверочным символам элементов И 8 -8„, которые соответствуют ненулевым символам синдрома.

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

Если один ошибочный символ попадает на информационйый разряд, а все остальные ошибочные символы — на проверочные разряды, то ошибки исправляются в течение одного из k последующих шагов до прихода следующего тактоврго импульса (т.е. между каждыми двумя тактовыми импульсами происходят (k+1) шагов декодирования) .

Второй шаг декодирования происходит при прохождении первого импульса от генератора 9 через элемент И 8„+„.

Этот импульс осуществляет один сдвиг в генераторе 4 и распределителе 5 импульсов. После этого сдвига на первом выходе распределителя 5 оказывается сигнал "1", а на всех других ег о выходах — сигнал "0" . Сиг нал "1" с первого выхода распределителя 5 осуществляет параллельную запись в генератор 4 последних k стюлбцов проверочной матрицы двоичного вектора, соответствующего (n-k+1)-Му столбцу проверочной матрицы. Одновременно сигнал "1" подается и на управляющий вход порогового элемента, в результате чего меняются величины его порогового значения t на значение (t-1). До окончания данного такта величина порога более не переключается.

Если один ошибочный символ попадает на (n-k+1)-й разряд кодовой комбинации (т. е. на первый,информационный разряд), а все остальные ошибочные символы — на первые (n-k) разрядов (проверочные разряды), то вектор синдрома отличается от (n-k+1)-го столбца проверочной матрицы не более чем

5 14293 в (t-1) символах, причем номера отличающихся символов соответствуют номерам пораженных ошибками проверочных разрядов. Таким образом, в указанном случае срабатывает пороговый эле- 5 мент 7, т.е. на его выходе возникает сигнал " 1". Этот сигнал проходит через те из элементов И 8,-8 „ „, ко1!орйе соответствуют номерам отличаю-;, щихся разрядов в векторе синдрома и 1О (и-k+1) ì столбце проверочной матрицы, т.е. номерам ошибочных проверочНых символов. В результате значения этих проверочных символов в буферном регистре 1 изменяются на противополож-15 ные, а ошибки в этих символах исправляются. Одновременно сигнал с выхода порогового элемента проходит через элемент И 8 „„„, открытый по пер;вому входу сигналом с выхода распре,делителя 5, и изменяет значение (n-1+1)-го (ошибочного) символа. Если распределение ошибочных символов в кодовой комбинации иное,то процесс

25 исправления ошибок продолжается.

Третий шаг декодирования происходит при появлении второго импульса на выходе элемента И 8„, Этот импульс производит сдвиг в генераторе 4, в результате в нем оказывается записанным кодовый вектор, соответствующий (n-k+2)-му столбцу проверочной матрицы. Кроме того, происходит также сдвиг в распределителе 5 импульсов, а сигнал "1" появляется на его втором 35 выходе. Если один ошибочный символ приходится на (n k+2)-й разряд кодовой комбинации, а остальные — на первые (n-k) разрядов, то точно так же, как и в предыдущем случае, все ошибки исправляются, Аналогично происходят и дальнейшие шаги декодирования, вплоть до (k+1)го шага. По окончании последнего (k+1)-го шага сигнал "1" возникает на (k+1)-и выходе распределителя S u устанавливает в состояние 0 триггер

3. В результате сигнал с второго вы-. хода этого триггера устанавливает на !! !! 50 0" генератор 2 синдрома и генератор

4, а также переводит в исходное состояние пороговый элемент 7. Если хоть при одном из (k+1) шагов декодирования на выходе порогового элемента 7 оказывается сигнал "1", то все оши55 бочные символы исправляются, В противном случае исправление ошибок может пр оиз ойти при одном из последую25 6 ших (и-1) тактов работы устройства декодирования.

Каждый новый такт начинается с приходом очередного импульса на вход тактовых импульсов. При этом происходят циклический сдвиг содержимого буферного регистра 1, а также сдвиг в генераторе 2 синдрома, в результате чего на выходах последнего возникнет синдром, соответствующий сдвинутой кодовой комбинации в буферном регистре 1. С приходом каждого тактового импульса триггер 3 переводится в состояние "1", в результате происходят укаэанные (k+1) шагов декодирования. Таким образом, весь процесс декодирования осуществляется за n(k+

+1) шагов, а исправление ошибок происходит лишь при одном иэ этих шагов, либо когда все ошибочные символы попадают на позиции проверочных разрядов, либо когда один ошибочный символ попадает на какую-либо из позиций информационных разрядов, а остальные ошибочные символы — на позиции проверочных разрядов. По окончании и тактов и, соответственно, п сдвигов в буферном регистре 1 в последнем вновь оказывается записанной исходная кодовая комбинация с исходным порядком следования символов, однако с исправленными ошибками.

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

k 2 где n — длина кода", k - число информационных симво!"лов;

t — число исправляемых кодом ошибок.

Этому соотношению удовлетворяют все известные короткие циклические коды (при и «б 45) и многие более длинные коды, Формула изобретения

1. Устройство для декодирования циклических кодов, содержащее п-раз-, рядный буферный регистр и генератор синдрома, сигнальные и !тактовые вхо- ды которых объединены и являются

1429325 сигнальным и тактовым входами устройства соответственно, группу иэ и элементов И, элемент И, распределитель импульсов и триггер, выход и разрядного буферного регистра является .выходом устройства, о т л и ч а ющ е е с я тем, что, с целью повышения надежности устройства путем упрощения, в него введены генератор ! (n-1с)-разрядного кода, где k - число информационных разрядов и-разрядного . кода, генератор импульсов, пороговый элемент и элементы ИСКЛЮЧИОЩЕЕ ИЛИ, выходы генератора синдрома и генератора (n-k)-разрядного кода соединены соответственно с первыми и вторыми входами соответствующих элементов

ИСКЛЮЧАЮЩЕЕ ИЛИ, выходы которых соединены с сигнальными входами порогового элемента и первыми входами первых (n-К)-элементов И группы, первые

k выходов распределителя импульсов соединены с первыми входами остальных элементов И группы, выход hop6ro-25 вого элемента соединен с вторыми входами всех элементов И группы, выходы которых соединены с входами соответствующих разрядов и-разрядного буферного регистра, первый выход распределителя импульсов соединен с входом управления порогового элемента и входом записи генератора (n-k)-разрядного кода, (k+1)-й выход распределителя импульсов соединен с R-входом триггера, S-вход которого подключен к тактовому входу устройства, инверсный выход триггера соединен с входа:ми установки генератора (n-К)-разрядного кода и порогового элемента, прямой выход триггера соединен с первым входом элемента И, второй вход которого соединен с выходом генератора импульсов, выход — с входом сдвига генератора (n-k)-разрядного кода и входом распределителя импульсов.

2. Устройство по п. 1, о т л и— ч а ю щ е е с я тем, что пороговый элемент содержит триггер, компаратор, ограничительные элементы и две группы согласующих элементов, йрямой и инверсный выходы триггера соединены с входами соответственно первого и второго согласующих элементов первой группы, выходы которых объединены и соединены с первым входом компаратора и входом первого ограничительного элемента, выходы согласующих элементов второй группы объединены и соединены с вторым входом компаратора и входом. второго ограничительного элемента, выходы ограничительных элементов объединены H подключены к шине положительного потенциала, S-входы триггера и входы согласующих элемен- тов второй группы являются соответственно входом установки, входом управления и соответствующими сигналь-. ными входами порогового элемента, выход компаратора является выходом порогового элемента.

14 29325

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

Редактор И.Шулла Техред Л.Олийнык Корректор М.Демчик

Заказ 5144/56 Тираж 929 Подписное

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

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

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