Декодирующее устройство для исправления пакетных ошибок

 

Изобретение относится к вычислительной технике. Его использование в системах передачи и обработки цифровой информации позволяет по высить достоверность декодирования. Декодирующее устройство для исправления пакетных ошибок содержит регистры 1, 2 сдвига, вычислитель 3 синдрома, блоки 4, 5 ключей, ключи 6-10, анализатор 12 синдрома и программно-временной блок 14. Введение ключа 11, анализатора 13 синдрома и элемента ИЛИ 15 обеспечивает в качестве декодированнот О варианта то кодовое слово , которому из всех пакетов ошибок наименьшей длины соответствует пакет наименьшего веса. 2 з.п..ф-лы, 5 ил. (Л

А1

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

СОЦИАЛИСТИЧЕСНЮ(РЕСПУБЛИН

„„Я0„„13 (51) 4 Н 03 М 13/00 р р 1 (\

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

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

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

К ABTOPGHOMV СВИДЕТЕЛЬСТВУ (2l) 3930342/24-24 (22) 12.07.85 (46) 30.03.87. Бюл. ¹ 12 (71) Ленинградский институт авиацион-. ного приборостроения (72) Г.С.Евсеев, E.À.Крук, В.П.Лавров и С.В.Семенов (53) 681.32(088.8) (56) Питерсон У. и Уэлдон Е. Коды, исправляющие ошибки. М.: Мир, 1976, стр. 213-218.

Касами Т. и др. Теория кодирования. М.: Мир, 1978, стр.403-405. (54) ДЕКОДИРУКМЦЕЕ УСТРОЙСТВО ДЛЯ

ИСПРАВЛЕНИЯ ПАКЕТНЫХ ОШИБОК (57) Изобретение относится к вычислительной технике. Его использование в системах передачи и обработки цифровой информации позволяет повысить достоверность декодирования. Декодирующее устройство для исправления пакетных ошибок содержит регистры 1, 2 сдвига, вычислитель 3 синдрома, блоки 4, 5 ключей, ключи 6-10, анализатор 12 синдрома и программно-временной блок 14. Введение ключа 11, анализатора 13 синдрома и злемента

ИЛИ 15 обеспечивает в качестве декодированного варианта то кодовое слово, которому из всех пакетов ошибок наименьшей длины соответствует пакет наименьшего веса. 2 э.п.. ф-лы, 5 ил.

1300645

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

Цель изобретения — повышение достоверности декодирования.

На фиг.! представлена блок-схема декодирующего устройства для исправления пакетных ошибок; на фиг.2— функциональная схема конкретного вы- 10 полнения вычислителя синдрома; на фиг. 3 — схема первого анализатора синдрома; на фиг.4 — схема второго анализатора синдрома; иа фиг. 5— временные диаграммы работы блока управления.

Декодирующее устройство для исправления пакетных ошибок содержит первый и второй регистры 1 и 2 сдви)

ra, вычислитель 3 синдрома, первый и второй блоки 4 и 5 ключей, первый— шестой ключи 6"11, первый и второй анализаторы 12 н 13 синдрома, программно-временной блок 14 и элемент

l5 HJIH. На фиг.l обозначены вход 16, информационный выход 17 и выход 18 синхронизации.

Вычислитель 3 синдрома представляет собой кодовый фильтр и для слу° чая линейного циклического (15, 9) кода с порождающим многочленом g(x)=

= х + х + х "+ хь+ l выполнен (фиг.2) на полусумматорах )9 и триггерах 20. На фиг.2 обозначены первый и второй информационные входы 21 и 22, управляющий вход 23, первый и вторые выходы 24 и 25 °

Первый анализатор 12 синдрома выполнен (фиг.3) на селекторе 26, бло- щ ке 27 ключей, блоке 28 сравнения и буферном регистре 29. На фиг.3 обозначены информационные входы 30, первый и второй управляющие входы 31 и

32, выходы 33. Селектор 26 служит для д5 выделения старшей значащей цифры и может быть реализован как логическая схема, каждый выход у. которой связан т со входами х зависимостью у = х . х

I 1 х х, ° ° ° х ) 1 е ()у Г)э Г число 5О проверочных символов.

Второй анализатор 13 синдрома выполнен (фиг.4)на блоке 34 взвешивания кода, блоке 35 ключей, блоке 36 сравнения и буферном регистре 37. На фиг.4 обозначены информационные входы

38, первый и второй управляющие входы 39 и 40, выход 41. Блок 34 взвешивания кода служит для подсчета числа единиц в синдроме и может быть выполнен на оперативном запоминающем устройстве (ОЗУ), в котором записаны веса всех r-ичных векторов.

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

14. Первый выход блока 14 подключен к первым управляющим входам анализаторов 12 и 13, второй и третий выходы — к управляющим входам соответственно первого и пятого ключей 6 и 10, четвертый выход — к первым управляющим входам ключей 7-9, пятый выход— к управляющим входам регистров 1 и 2 сдвига и вычислителя 3 синдрома, шестой выход блока 14 является выходом

18 синхронизации. Сигналы на соответствующих выходах программно=временного блока 14 приведены на диаграммах фиг.5.

Декодирующее устройство для исправления пакетных ошибок работает следующим образом.

В исходном положении ключи 6-9 открыты, а блоки 4 и 5 ключей и ключи 10 и 11 закрыты, первый и второй регистры 1 и 2 сдвига, а также вычислитель 3 синдрома находятся в нулевом, а регистр 29 анализатора 12 и регистр 37 анализатора 13 — a единичном состоянии.

l. В режиме приема переданного слова со входа 16 п символов (п — длина используемого кода) последовательно поступают через открытый ключ 6 на первые информационные входы первого и второго регистров 1 и 2 сдвига и вычислителя 3 синдрома, в которых одновременно осуществляются циклические сдвиги (ключи 7-9 открыты).

Зти сдвиги управляются сигналами, одновременно поступающими на управляющие входы первого и второго регистров 1 и 2 сдвига и вычислителя синдрома 3 с пятого выхода программновременного блока 14. В результате через и тактов (п циклических сдвигов) принятое слово записывается в регистрах 1 и 2 сдвига, а синдром принятого слова — B вычислителе 3 синдрома.

2, После приема слова осуществляется режим декодирования. В этом режиме первый ключ 6 закрывается уп130064 равляющим импульсом со второго выхода блока 14. В режиме декодирования осуществляются следующие операции.

2.1. Символы синдрома с выходов вычислителя 3 синдрома параллельно поступают на информационные входы анализатора 12, преобразуются в се . лекторе 26 в число ?, где 1 — длина пакета на синдроме, которое сравнивается в блоке 28 сравнения с числом,10 записанным в регистре 29. Одновременно символы синдрома с выходов вычислителя .3 синдрома параллельно поступают на информационные входы анализатора 13. В блоке 4 определяется вес 15 синдрома, который затем сравнивается в блоке 36 сравнения с записанным в регистре 37 весом маркерного пакета.

Если число, поступающее с выходов вычислителя 3 синдрома, строго меньше 20 числа, поступающего с выходов регистра 29, то на первом выходе блока 28 сравнения появляется импульс, который поступает на первый вход элемента

ИЛИ 15. 25

Если число, поступающее с выходов вычислителя 3 синдрома на входы блока 28 сравнения, равно записанному в регистре 29 числу, то импульс со второго выхода блока 28 сравнения откры-30 вает шестой ключ 11. В случае, когда этот ключ 11 открыт, импульс с выхода блока сравнения 36 (этот импульс появляется, если вес пакета на синдроме меньше хранимого в регистре 37 35 веса маркерного пакета) поступает через ключ 11 на второй вход элемента

ИЛИ 15.

Таким образом, импульс на выходе элемента ИЛИ 15 появляется в том и 40 только в том случае, когда-либо найдет пакет на синдроме более короткий, чем ранее просмотренные, либо найден пакет, длина которого равна длине маркерного, а вес меньше. 45

5 4

Содержимое вычислителя 3 синдрома и блока 34 вычисления веса при открытых блоках 27 и 35 ключей переписывается соответственно в регистры

29 и 37.

В результате проведенных операций (пункты 2.1 и 2.2) в регистре 29 будет записан синдром, соответствующий пакету, который имеет минимальный вес среди пакетов, имеющих минимальную длину среди всех просмотренных, в регистр 37 будет записан вес этого пакета, а в первом регистре 1 сдвига будет записан соответствующий этому пакету вариант декодированного слова.

2.3. С пятого выхода блока 14 на управляющие входы регистров 1 и 2 сдвига и вычислителя 3 синдрома поступает импульс, по которому производится циклический сдвиг их содержимого. Затем повторяются операции по пунктам 2.1, 2 ° 2, циклический сдвиг проводится п раз (и — длина кодового слова).

В результате этапа 2 в первом регистре 1 сдвига будет записан декодированный вариант принятого слова, 3. По окончании декодирования начинается этап выдачи декодированного слова. Импульсом с четвертого выхода блока 14 ключи 7-9 закрываются. Одновременно ключ !0 открывается импульсом с третьего выхода блока 14. 3а п тактов содержимое первого регистра

1 сдвига (декодированное слово) выдается в последовательном коде через открытый пятый ключ 10 на выход 17 устройства. При этом содержимое регистров 1, 2 и вычислителя 3 синдрома обнуляется.

После выдачи результата декодирования импульсы с первого, второго, третьего и четвертого выходов блока

14 устанавливают все ключевые элементы и ячейки памяти в исходное поло2.2. ИмпуЛьс с выхода элемента

ИЛИ 15 открывает блоки 4, 5, 27, 35 ключей, закрывает ключи 7-9 и обну, ляет содержимое первого регистра 1 сдвига. При закрытых ключах 7-9 цепи обратной связи регистров 1 и 2 сдвига и вычислителя 3 синдрома разрываются и содержимое вычислителя 3 синдрома подается на входы г (г — число 55 проверочных символов кода) левых разрядов первого 1 регистра сдвига, где складывается по модулю два с содержимым второго регистра 2 сдвига, жение.

Если пакет исправляем кодом, то на одном из циклических сдвигов синдрома этот пакет окажется записанным в крайних левых ячейках вычислителя 3 синдрома, при этом число на выходе селектора 26

"примет минимальное на всех сдвигах значение, а число на выходе блока 34 (вес пакета) будет минимальным среди всех сдвигов, которым соответствует минимальная длина пакета. По окончании декодирования получателю будет выдано слово, соответствующее исправ5 130064 лению именно этого пакета, Таким образом в случае наличия двух и более пакетов одинаковой длины, которые могли бы привести к появлению принятого слова, в качестве декодированно- 5 го варианта будет выбрано слово, которому соответствует более вероятный пакет — меньшего веса. Это обеспечивает преимущество данного устройства по вероятности ошибочного декодирова- !О ния по сравнению с известным устройством, в котором в указанной ситуации декодирование не всегда проходит в пользу более вероятного вектора, 15

Таким образом, применение декодирующего устройства для исправления пакетных ошибок позволяет осуществить оптимальное декодирование в каналах с малой плотностью пакетов ошибок и

20 тем самым повысить достоверность передачи информации в таких каналах.

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

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

35 первого и второго регистров сдвига и вычислителя синдрома, вторые выходы вычислителя синдрома и второго регистра сдвига подключены к соответствующим информационным входам соответственно первого и второго блоков ключей, выходы которых соединены соответственно с третьими и четвертыми информационными входами первого регистра сдвига, второй выход которого соединен с информационным входом пятого ключа, вторые выходы вычислите ля синдрома подключены к соответствукнцим информационным входам первого анализатора синдрома, программновременной блок, первый, второй и третий выходы которого подключены соответственно к первому управляющему входу первого анализатора синдрома и управляющим входам первого и пятого ключей, четвертый выход программновременного блока соединен с первыми управляющими входами второго, тре5 6 тьего и четвертого ключей, вторые управляющие входы которых объединены с управляющими входами блоков ключей и вторым управляющим входам первого анализатора синдрома, пятый выход программно-временного блока подключен к первому управляющему входу первого регистра сдвига и управляющим входам второго регистра сдвига и вычислителя синдрома, вход первого ключа является входом устройства, выход пятого ключа и шестой выход программно-временного блока являются соответственно информационным выходом и выходом синхронизации устройства, о т— л и ч а ю щ е е с я тем, что, с целью повышения достоверности декодирования, в устройство введены шестой ключ, элемент ИЛИ и второй анализатор синдрома, первый управляющий вход которого подключен к первому выходу программно-временного блока, вторые выходы вычислителя синдрома подключены к соответствующим информационным входам второго анализатора синдрома, выход которого соединен с информационным входом шестого ключа, первый и второй выходы первого анализатора синдрома соецинены соответственно с первым входом элемента ИЛИ и управляющим входом шестого ключа, выход которого соединен с вторым входом элемента ИЛИ, выход которого подключен к вторым управляющим входам анализаторов синдрома и первого регистра сдвига.

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

3 е УСтРОИСтВО IIO II ° 1 р О T Л И ч а ю щ е е с. я тем, что второй ана7 1300б45 8 лизатор синдрома выполнен на буферном подключены к соответствующим вторым регистре, блоке сравнения, блоке клю- входам блока сравнения, входы блока чей и блоке взвешивания кода, выходы взвешивания кода являются информакоторого соединены с соответствующими ционными входами анализатора, управпервыми входами блока сравнения и 5 ляющие входы буферного регистра и блоинформационными входами блока ключей, ка ключей являются соответственно выходы которого соединены с соответ- первым и вторым управляющими входами ствующими информационными входами бу- анализатора, выход блока сравнения ферного регистра, выходы которого является выходом анализатора.

gf

Фиг.2

1300645

Составитель О.Ревинский

Техред А.Кравчук Корректор А. Зимокосов

Редактор М,Сегляник

Тираж 902 Подписное

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

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

Заказ 1160/56

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