Помехоустойчивый кодек для передачи дискретных сообщений

 

Изобретение относится к технике связи и вычислительной технике и может быть использовано в системах пепедячи дискретной информации,, Цель изобретения - повышение информативности о Для этого кодируют элементарные дискретные сообщения неравномерными кодовыми комбинациями, формируют их в группу длиной К двоичных символов, формируют маркерный код незаполненных К-К позиций и размещают этот маркерный код на 1 позициях после группы из К символов о После этого группа К+1 символов кодируется помехоустойчивым блоковым кодом с г проверочными символами В декодере осуществляется исправление ошибок, выделение маркерного кода и разделение кодовых комбинаций. 3 ил ,, 1 табл„ (Л

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

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

РЕСПУБЛИК..SU„„

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

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

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

ПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ

ПРИ ГКНТ СССР

° (21 ) 4664539/24 (22) 20.03.89 (46) 23.05.91. Бюл. ¹ 19 (71) Гродненский государственный университет (72) В.Н.Сюрин, Б;А.Ассанович, Я1.В.Беланович и В.M.Äóáêo (53) 621 .394 .14 681 .326(088.8) (56) Дмитриев В.И. Прикладная теория информации. — М.: Высшая школа, 1989, с.193-196.

Патент СИА № 4646061, кл. Н 03 M 7/42, опублик. 1987.

Авторское свидетельство СССР № 995355, кл. H 04 1 17/00, 1981. (54) ПОМЕХОУСТОЙЧИВЫЙ КОДЕК ДЛЯ ПЕРЕДАЧИ ДИСКРЕТНЫХ СООБЩЕНИЙ (57) Изобретение относится к технике

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

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

На фиг.1 и 2 изображены блок-схемы соответственно кодера и декодера; на фиг„3 — схема формирования кодового слова.

Помехоустойчивый кодек состоит из кодера и декодера.

Кодер содержит первый и второй блоки i и 2 постоянной памяти, первый и второй регистры 3 и 4 сдвига, формирователь 5 проверочных символов, делитель 6 частоты, триггер 7, форми(5g)g H 03 M 13/00, 7!42, 7/46

2 связи и вычислительной технике и может быть использовано в системах пепедачи дискретной информации. Цель изобретения — повышение информативности. Для этого кодируют элементарные дискретные сообщения неравномерными кодовыми комбинациями, формиру! ют их в группу длиной К двоичных символов, формируют маркерный код незаполненных К-К позиций и размещают этот маркерный код на 1 позициях после группы из К символов, После этого группа К+1 символов кодируется помехоустойчивым блоковым кодом с r проверочными символами. В декодере осуществляется исправление ошибок, CJ выделение маркерного кода и разделение кодовых комбинаций. 3 ил., 1 табл. рователь 8 импульсов, первый и второй счетчики 9 и 10 импульсов, элемент

И 11, источник 12 постоянного кода, компаратор 13, информационные входы

14 и тактовый вход 15.

Декодер содержит (фиг. 2) блок 16 коррекции ошибок, первый и второй регистры 17 и 18 сдвига, первый и

1второй блоки 19 и 20 постоянной памяти, первый-третий элементы

И 21-23, первый — третий счетчики 2426 импульсов, генератор 27 импульсов, первый и второй триггеры 28 и 29, компарат р 30, дешифратор 31, элемент

ИЛИ 32, информационный вход 33 и тактовый вход 34.

165)385. Блоки 1, 2, 19 и 2О постоянной памяти представляют собой ПЗУ.

Формирователь 5 проверочных символов реализуется, например, на сумматорах по модулю два в соответствии с применяемым помехоустойчивым кодом.

Формирователь 8 импульсов выполнен в виде ждущего мультивибратора.

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

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

При построении такого неравномерного кода необходимо учесть требова- 25 ння однозначности декодирования. Для однозначности декодирования необходимо, чтобы ни одна кодовая комбинация меньшей длины не совпадала с началом кодовой комбинации большей 3р длины, т.е. код должен обладать свойством неприводимости. В качестве при.мера рассмотрим неравномерный двоичный код Шеннона-Фано. Соответствие неравномерных кодовых комбинаций 35 элементарным сообщениям источника с учетом априорной вероятности их появления Р; (х) показано в таблице.

После такого кодирования формиру- 4р ется блок фиксированной длины, содержащей п двоичных посылок (фиг.З).

Из и посылок r являются .проверочными, формируемыми в соответствии с выбранным блочным кодом. Значения этих r 45 посылок определяются в зависимости от значений посылок, входящих в группы К и 1. Группа К,составляется из совокупности неравномерных, кодовых комбинаций, соответствующих элементарным сообщениям, произвольным образом поступающим от источника и подлежащим передаче, поэтому из-за неравномерности этих кобинаций граница t является плавающей. Это значит, что в общем случае не все К позиций заполняются ннформационньпчи посылками, при поступлении очередной неравномерной комбинат;ии при формировании кодового блока может оказаться, что свободное расстояние 1 меньше, чем длина этой комбинации. В этом

4 случае 1 позиций остаются свободными а поступившая неравномерная комбинация будет использована в качестве первой для формирования следующего кодового блока из и посылок. Из К посылок информационными будут являться К позиций. Для правильного

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

1 от блока к блоку границу t. Кодирование местоположения границы t или (Ф то же самое длины группы 1, производится с помощью служебной группы 1 фиксированной длины, эта группа представляет собой двоичное число отоб(Э

I ражающее длину группы 1, выраженную в количестве двоичных посылок. Еслй

f учесть, что 1 может принимать значения 0,1,2,,(lìàêñ 1) где 1м((кс максимальная длина неравномерных кодовых комбинаций, то длина 1 определяется как 1 1оЫмак . Итак, группы r и 1 имеют фиксированную дли(» ну, группа 1 — свободные позиции от конца группы К переменной длины до начала группы 1, значения посылок группы 1 есть двоичное число выражают

Э щее длину группы 1

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

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

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

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

В кодере с входов 14 на адресные входы первого и второго блоков 1 и 2 постоянной памяти поступают днскрет.-.

1651385 6 ные сообщения в виде равномерных двоичных комбинаций. По переднему фронту импульса, приходящего с выхода делителя б, коэффициент деления которого равен числу двоичных разрядов, соответствующих неравномерной кодовой комбинации максимальной длины, из первого блока 1 разрешается выборка соответствующей неравномерной кодо" вой комбинации, а из второго блока <

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

9, информация, выбранная из блоков

1 и 2, подается на гараллельные входы первого регистра 3 сдвига и первого счетчика 9 импульсов и записывается в них, С приходом этого же импульса на S-вход триггера 7 послед-. ний устанавливается в единичное состояние и разрешает запуск .формирователя 8 тактовыми импульсами, приходящими с входа 15 через открытый по второму входу элемент И 11. Импульсы с выхода формирователя 8 поступают на тактовый вход первого счетчика

9, который работает на уменьшение счета, и на тактовые входы первого

3 и второго 4 регистров сдвига, осуществляя сдвиг неравномерной кодовой комбинации из регистра 3 в регистр 4 на определенное число разрядов, saписанное в двоичном коде в первом счетчике 9. После обнуления счетчика

9 перепад логического уровня с выхода окончания счета этого счетчика поступает на R-вход триггера 7, переключая его в нулевое состояние и останавливая тем самым запуск формирователя 8 очередным тактовым импульсом, приходящим с входа 15. Неравномерная кодовая комбинация оказывается записанной во втором регистре 4.

Триггер 7, формирователь 8, первый счетчик 9 с заведенной с его выхода обратной связью представляют собой программируемый генератор импульсов, выдающий заданное, записанное в двоичном коде в счетчик 9 количество импульсов, соответствующее числу.рарядов каждой неравномерной кодовой комбинации.

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

l

Как только число свободных 1 позиций окажется меньше числа позиций очередной кодовой комбинации, на выходе компаратора 13 появится логический сигнал, запрещающий запуск формирователя 8. Этот же логический сигнал поступает на вход разрешения параллельной загрузки регистра 4 сдвига и на управляющий вход формирователя 5 проверочных символов и разрешает запись с выходов счетчика 10 двоичного кода, соответствующего числу оставшихся незанятыми 1 позиций кодового слова, в отведенные для этой цели 1 позиций, а также разрешает формирование проверочных посылок и запись их в соответствующие

r позиций регистра 4. Сигнал с выхода компаратора 1 3 поступает также во второй регистр 4, накапливаясь в нем.

Импульсы с выхода формирователя 8

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

I числу 1 оставшихся незанятыми позиций информационной части кодового

I слова, поступает на вторые входы цифрового компаратора 13, на первые входы которого из второго блока 2 постоянной памяти поступает двоичный

20 код, соответствующий числу позиций, занимаемых очередной передаваемой неравномерной кодовой комбинацией. В компараторе 13 происходит сравнение этих двух двоичных чисел. Если число

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

30 на выходе компагатора 13 логический уровень, поступающий на второй вход элемента И 11 разрешает запуск формирователя 8 тактовыми импульсами, приходящими на его тактовый вход, 35 H очередная нераВНОмерняя кодова комбинация будет поразрядно загисываться во второй регистр 4 сдвига, где происходит формирование передаваемого кодового блока.

1651385

20 на вход разрешения параллельной загрузки счетчика 10 и разрешает запись первоначального значения К позиций информационной части кодового слова от источника 12 постоянного кода в этот счетчик 10. Двоичный код, соответствующий числу К, появится на вы/ходах счетчика 10, а значит, и на вторых . входах компаратора 1 3, на первых входах которого будет присутствовать двоичный код, соответствующий числу позиций очередной подлежащей передаче кодовой комбинации.

В результате сравнения на выходе 15 компаратора 13 произойдет смена логического сигнала, что разрешит прохождение тактовых импульсов через элемент И 11, запускающих формирователь

8, который сдвигает записанную в регистре 3 очередную кодовую комбинацию и поразрядно.-записывает ее в регистр 4, из которого одновременно с записью происходит поразрядная выдача посылок сформированного прежде кодового блока. Таким образом, процесс формирования и выдача в канал связи (не показан) информации будут проходить одновременно, без задержки времени. Далее периодичес- 30 ки формируются последующие кодовые блоки из и символов.

В декодере кодовый блок из канала связи через вход 33 последовательно поступает на вход блока 16 коррекции ошибок, в котором происходит вычисление контрольных сумм составляющих синдрома. В случае, когда значение синдрома отлично от нуля, по его значению в блоке 1 6 коррекции пронсхо- 40 дит определение местоположения ошибочно принятых информационных посылок и их замена на правильные.

Тактовые импульсы, частота следования которых подбирается так, чтобы 45 в момент полной записи принятого кодового блока в блок 16 полностью очистился регистр 1 7 сдвига длиной в n-r ячеек, поступают с входа 34 на тактовый вход счетчика 25 н íà 50 объединенные тактовые входы регистров 17 и 18 сдвига, длина которого выбирается равной максимальному числу позиций, занимаемых неравномерной кодовой комбинацией и осуществляют сдвиг и-r информационных посылок, переписываемых каждый раз в регистр

l7 из блока 16 после получения нового кодового слова.

Таким образом, после полного заполнения счетчика 25, коэффициент пересчета которого также равен n-r, на его выходе появляется логический сигнал поступающий на управляющий вход блока 16 коррекции и на входы разрешения параллельной загрузки регистра 17 сдвига и счетчика 21, разрешая параллельную запись из блока

16 исправленных информационных n-r посыпок в регистр 17, а из соответствующих 1 позиций регистра 1 7 двоичного кода, соответствующего длине служебной группы 1, — в счетчик 24. (I

Счетчик 24, предстарляющий собой двоичный счетчик с предварительной записью, коэффициент пересчета которого выбирается равным К, подсчитыва-.: ет число тактовых импульсов, поступающих с входа 34 на его вход через открытый по второму входу третий элемент И 23 и определяет число К поФ зицни, занимаемых принятыми неравномерными кодовыми комбинациями, входящими в данный кодовый блок, а значит, и плавающую границу t для этого блока.

После полного заполнения счетчика

24 на его выходе появляется логический сигнал, поступающий íà R-вход первого триггера 28 и перебрасывающий его в нулевое состояние, запрещая тем самым прохождение тактовых импульсов на вход счетчика 24 через элемент И ?3. Этот же логический сигнал с выхода триггера 28 поступает на второй вход первого элемента И 21 и запрещает последовательное поступление во второй регистр 1 8 оставшихся записанными в первом регистре 1 7 служебных групп посылок 1 к 1

Соответствующие выходы второго регистра 1 8 соединены параллельно с адресными входами первого блока 19 постоянной памяти и с первыми входами цифрового компаратора 30. Тактовые импульсы, поступающие íà S-вход второго триггера 29, устанавливают его каждый раз в единичное состояние, разрешая тем самым прохождение импульсов с выхода генератора 27 через второй элемент И 22, открытый по первому входу логическим сигналом с выхода первого триггера 28. Эти импульсы с генератора 27 начинают проходить с момента начала п разрядного поступления неравномерных кодовых комбинаций очередного принятого блока во второй

1651385

40

Ъ регистр 18. Импульсы с выхода генератора 27, частота которого выбирается больше частоты следования тактовых импульсов в число ра=, равное числу всевозможных неравномерных кодовых комбинаций, соответствующих алфавиту источника сообщения, подсчитываются третьим счетчиком 26, на выходах которого формируется адрес, параллельно 10 поступающий на соответствующие адресные входы второго блока 20 постоянной памяти и на вторые входы компаратора 30.

В результате сравнения кодовой комбинации, поразрядно записываемой во второй регистр 18 сдвига, с выбираемыми из второго блока 20 известными получателю неравномерными кодовыми комбинациями источника при сов- 2р падении двух комбинаций, поступающих на соответствующе входы компаратора

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

30, поступающим на первый вход элемента ИЛИ 32 или же (в случае ненахождения кодовой комбинации, эквивалентной записанной в этот момент во втором регистре !8) сигналом с выхода дешифратора 31, который появляется после заполнения счетчика 26 и просмотра всех возможных адресов и поступает на второй вход элемента

ИЛИ 32, перебрасывается в нулевое состояние второй триггер 29, сигнал с которого поступает на третий вход второго элемента И 22 и запрещает прохождение импульсов с выхода генератора 27 на вход третьего счетчика 45

?6. С приходом следующего тактового импульса на объединенные тактовые входы регистров 17 и 18 сдвига, а тякж на S-вход второго триггера ?9 содержимое регистров 17 и 18 сдвигается на одну позицию вправо, а триггер 29 перебрасывается в единичное

° состояние, разрешая прохождение импульсов через второй элемент И 22 на вход третьего счетчика 26.

Таким образом, процесс формирования- адресов счетчиком 26, просмотр содержимого второго блока 20 постоянI ной памяти и сравнение кодовых комбинаций в компараторе 30 повторяются снова и завершаются после поразрядного прохождения через второй регистр

18 всех информационных посылок групА пы К,поступающих из первого регистра 17 сдвига, до те пор, пака не заполнится счетчик 24 и не перебросит первый триггер 28 в нулевое состояние, запрещая прохождение информационных посылок по второму входу первого элемента И 21 на вход регистра

18.

Следующий цикл обработки нового кодового блока, поступающего на вход

33 декодера, начнется после заполнения счетчика 25 и выдачи им нового сигнала разрешения.

Таким образом, процесс приема, т.е. записи кодового блока в блок 16 коррекции ошибок, и обработка предыдущего информационного блока происходит непрерывно.

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

Хэмминга, исправляющий однократную ошибку. Для него п127, r=7 и для вышеприведенных (фиг.3) обозначений

К+1=120. Пусть передаче подлежат элементарные сообщения, кодируемые неравномерными комбинациями согласно приведенной таблице. Для этой таблицы 1макс=4. Тогда 1 = logzl aкс

= log 4 = 2 и К=118, т„е. для кодирования длины 1 отводится две позиции, ( а для размещения неравномерных инфор- мационных комбинаций — 118. Предположим, что от источника на передаче поступают 40 элементарных сообщений, в соответствии с вероятностями Р, (рассмотрим типичный случа, который имеет место в среднем) количество конкретных сообщений пх, будет равно пх 40 Р = 40 0 25 = 10;

Х I пх = 40 Р = 40 0,23 = 9,2 = 9; пх = 40 Рз = 400 15 = 61

n = 40 P = 40 0 1 = 4; к+ п = 40 P = 40 0 09 = 3 6 4

"5 5 и„= 40Р = 40 008 = 32 3;

"6 пх = 40 ° P7 = 40 0,07 = 2,8 =3;

n x = 40 P 8 = 40 О, 03 = 1, 2 -" 1 .

Тогда общее число двоичных сигналов для кодирования данной сов<куп)1 1651 ности сообщений в соответствии с таблицей будет равно

Б =, и„. n, = lO 2 + 9 ° 2 + 6 3 +

+ 4 3+ 4 ° 4+ 3 ° 4+3 ° 4+

+ 1 4 = 112.

В рассмотренном же кодеке для размещения неравномерных комбинаций отводится 118 позиций, значит, на оставшихся шести свободных позициях можно разметить еще определенное число комбинащлй, например х и х, тогда 1 =l и комбинация 1 будет иметь значение Ol, При использовании же равномерных комбинаций в кодовом блоке можно закодировать только 40 элементарных сообщений, так как каждое из них содержит три двоичных посылки, а для размещения отводится

120 позиций. Таким образом, при одинаковой достоверности (исправляется однократная ошибка) в рассмотренном кодеке передается на две комбинации

I больше .

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

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

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

- управляющему входу формирователя про=

20 верочных символов, выходы которого соединены с первыми установочными входами второго регистра сдвига, выход первого счетчика импульсов подключен к второму установочному вхо25 ду триггера, выходы источника постоянного кода подключены к установочным входам второго счетчика импульсов, выходы которого соединены с вторыми входами компаратора и вторыми уста30 новочными входами второго регистра сдвига, последовательный выход которого является выходом кодера, в декодер введены второй блок постоянной памяти, первый — третий счетчики импульсов, первый и второй триггеры. первый — третий, элементы И, генератор импульсов, дешифратор, компаратор и элемент ИЛИ, информационный вход блока коррекции ошибок является

Р, (х) Неравномерные кодовые комбинации двоичных сигналов

Элементарные сообщения источника

0,25

0,23

0,15

0,10

0,09

0,08 >,07

0i03

1 1

1 0

011

001 1

001 0

0001

0000 х х> х

5 х

Т хВ

1З 165 выход второго счетчика импульсов подключен к управляющему входу блока коррекции ошибок, второму установочному входу первого триггера и входам разрешения записи первого счетчика импульсов и первого регистра сдвига, последовательный выход которого соединен с вторым входом первого элемента И, выход которого подключен к информационному входу второго регистра сдвига, выходы которого соединены с адресными входами первого блока постоянной памяти и первыми входами компаратора, выходы генератора импульсов и второго триггера подключены к второму и третьему входам второго элемента И, в.хоп которого соединен со счетным входом третьего счетчика импульсов, выходы которого подключены к адресным входам второго блока постоянной памяти и входам дешифратора, выход которого соединен с первым входом элемента ИЛИ, выход которого подключен к второму устаI!

385 14 новочному входу второго триггера, выХоды второго блока постоянной памяти соединены с вторыми входами компаратора, выход которог подключен к j второму входу элемента ИЛИ и входу разрешения выборки первого блока постоянной памяти, выходы кот6рого являются выходами декодера.

1651 385

l l

6uz3

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

Техред А.Кравчук " Корректор С.Шекмар

Редактор С.Пекарь

Заказ 1611 Тираж 479 Подписное

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

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

Производственно-издательский комбинат "Патент", r. Ужгород, ул. Гагарина, 101