Помехоустойчивый кодек для передачи дискретных сообщений Советский патент 1991 года по МПК H03M13/00 H03M7/42 H03M7/46 

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

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

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

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

Кодер содержит первый и второй блоки 1 и 2 постоянной памяти, первый и второй регистры 3 и 4 сдвига, формирователь 5 проверочных символов, делитель 6 частоты, триггер 7, формирователь 8 импульсов, первый и второй счетчики 9 и 10 импульсов, элемент И 11, источник 12 постоянного кода, компаратор 13, информационные входы 14 и тактовый вход 15„

Декодер содержит () блок 16 коррекции ошибок, первый и второй регистры 17 и 18 сдвига, первый и (второй блоки 19 и 20 постоянной памяти, первый-третий элементы И 21-23, первый - третий счетчики 24- 26 импульсов, генератор 27 импульсов, первый и второй триггеры 28 и 29, компаратор 30, дешифратор 31, элемент ИЛИ 32, информационный вход 33 и тактовый вход 34

05 СЛ

со оо ел

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

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

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

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

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

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

I

После такого кодирования формиру-

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

кодового блока может оказаться, что свободное расстояние 1 меньше, чем длина этой комбинации В этом случае 1 позиций остаются свободными, а поступившая неравномерная комбинация будет использована в качестве первой для формирования следующего кодового блока из п посылок Из К посылок информационными будут являться K позиций Для правильного разделения неравномерных комбинаций на приеме и исключения вставок лишних комбинаций необходимо сформировать метку, определяющую местоположение конца группы К , т.е. плавающую от блока к блоку границу t. Кодирование местоположения границы t, или то же самое длины группы 1 , производится с помощью служебной группы 1 фиксированной длины, эта группа представляет собой двоичное число, отображающее длину группы 1 , выраженную в количестве двоичных посылок Если учесть, что I1 может принимать значения 0,1 ,2, ..„, ( -1) , где максимальная длина неравномерных кодовых комбинаций, то длина 1 определяется как 1 « log l/Maxe Итак, группы г и 1 имеют фиксированную длину, группа 1 - свободные позиции от конца группы К переменной длины до начала группы 1, значения посылок iгруппы 1 есть двоичное число, выражающее длину группы 1.

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

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

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

10

во второй регистр 4, накапливаясь нем.

Импульсы с выхода формировател поступают также на тактовый вход второго счетчика 40, представляющ собой реверсивный счетчик, работа щий на уменьшение счета, в которо первоначально из блока 12 записыв ся значение К, соответствующее об му числу свободных позиций для ин мационных ПОСЫЛОК, ДВОИЧНЫЙ КОД С ХОДОВ счетчика 10, соответствующи числу 1 оставшихся незанятыми по

ной загрузки регистра 3 и счетчика 9, информация, выбранная из блоков 1 и 2, подается на параллельные входы первого регистра 3 сдвига и первого счетчика 9 импульсов и записыва- 20 ется в них, С приходом этого же импульса на S-вход триггера 7 последний устанавливается в единичное состояние и разрешает запуск .формирователя 8 тактовыми импульсами, приходя- 25 щими с входа 15 через открытый по второму входу элемент И 11. Импульсы с выхода формирователя 8 поступают на тактовый вход первого счетчика 9, который работает на уменьшение 30 счета, и на тактовые входы первого 3 и второго 4 регистров сдвига, осуществляя сдвиг неравномерной кодовой комбинации из регистра 3 в регистр 4 на определенное число разрядов, записанное в двоичном коде в первом счетчцке 90 После обнуления счетчика 9 перепад логического уровня с выхода окончания счета этого счетчика поступает на R-вход триггера 7, переключая его в нулевое состояние и останавливая тем самым запуск Формирователя 8 очередным тактовым импульсом, приходящим с входа 15, Неравномерная кодовая комбинация оказывает- д5 ся записанной во втором регистре 4, Триггер 7, формирователь 8, первый счетчик 9 с заведенной с его выхода обратной связью представляют собой программируемый генератор импульсов,. 50 выдающий заданное, записанное в двоичном коде в счетчик 9 количество импульсов, соответствующее числу разрядов каждой неравномерной кодовой комбинации,55

I

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

35

40

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

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

ций информационной части кодового

во второй регистр 4, накапливаясь в нем.

Импульсы с выхода формирователя 8 поступают также на тактовый вход второго счетчика 40, представляющего собой реверсивный счетчик, работающий на уменьшение счета, в котором первоначально из блока 12 записывается значение К, соответствующее общему числу свободных позиций для информационных ПОСЫЛОК, ДВОИЧНЫЙ КОД С ВЫХОДОВ счетчика 10, соответствующий числу 1 оставшихся незанятыми пози05 0 5 0 5

5

0

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

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

на вход разрешения параллельной загрузки счетчика 10 и разрешает запись первоначального значения К позиций информационной части кодового слова от источника I2 постоянного кода в этот счетчик 0« Двоичный код, соответствующий К, появится на вы- /ходах счетчика 10, а значит, и на вторых - входах компаратора 13, на первых входах которого будет присутствовать двоичный код, соответствующий числу позиций очередной подлежащей передаче кодовой комбинации,

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

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

Тактовые импульсы, частота следования которых подбирается так, чтобы в момент полной записи принятого кодового блока в блок 16 полностью очистился регистр I1 сдвига длиной в п-г ячеек, поступают с входа 34 на тактовый вход счетчика 25 и на объединенные тактовые входы регистров 17 и 18 сдвига, длина которого выбирается равной максимальному числу позиций, занимаемых неравномерной кодовой комбинациейр и осуществляют сдвиг п-г информационных посылок, переписываемых каждый раз в регистр 17 из блока 16 после получения нового кодового слова.

Таким образом, после полного заполнения счетчика 25, коэффициент пересчета которого также равен п-г, на его выходе появляется логический сигнал, поступающий на управляющий вход блока 16 коррекции и на входы разрешения параллельной загрузки регистра 17 сдвига и счетчика 21, разрешая параллельную запись из блока 16 исправленных информационных п-г посыпок в регистр 17, а из соответствующих 1 позиций регистра 1 7 двоичного кода, соответствующего длине служебной группы 1 ,- в счетчик 24. Счетчик 24, представляющий собой двоичный счетчик с предварительной записью, коэффициент пересчета которого выбирается равным К, подсчитывав ет число тактовых импульсов, поступающих с входа 34 на его вход через открытый по второму входу третий элемент И 23 и определяет число К позиций, занимаемых принятыми неравномерными кодовыми комбинациями, входящими в данный кодовый блок, а значит , и плавающую границу t для этого блока

После полного заполнения счетчика 24 на его выходе появляется логический сигнал, поступающий на R-вход первого триггера 28 и перебрасывающий его в нулевое состояние, запреща тем самым прохождение тактовых импульсов на вход счетчика 24 через элемент И 23„ Этот же логический сигнал с выхода триггера 28 поступает на второй вход первого элемента И 21 и запрещает последовательное поступление во второй регистр J 8 оставшихс записанными в первом регистре 17 служебных: групп посылок 1 к „ Соответствующие выходы второго регистра 18 соединены параллельно с адресными входами первого блока-19 постоянной памяти и с первыми входами цифрового компаратора 30. Тактовые импульсы, поступающие на S-вход второго триггера 29, устанавливают его каждый раз в единичное состояние, разрешая тем самым прохождение импуль гов с выхода генератора 27 через второй элемент И 22, открытый по первому входу логическим сигналом с выхода первого триггера 28. Эти импульсы с генератора 27 начинают проходить с момента начала поразрядного поступления неравномерных кодовых комбинаций очередного принятого блока во второй

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

В результате сравнения кодовой комбинации, поразрядно записываемой во второй регистр 18 сдвига, с выбираемыми из второго блока 20 известными получателю неравномерными кодовыми комбинациями источника при сов- падении двух комбинаций, поступающих на соответствующе входы компаратора 30, на его выходе появляется логический сигнал, приходящий на вход разрешения выборки первого блока 19, разрешая выдачу первичной информации, хранящейся в этом блоке I9 и соответствующей данной неравномерной кодовой комбинациио Кроме того, этим же логическим сигналом с выхода компаратора 30, поступающим на первый вход элемента ИЛИ 32 или же (в случае ненахождения кодовой комбинации, эквивалентной записанной в этот момент во втором регистре 18) сигналом с выхода дешифратора 31, который появляется после заполнения счетчика 26 и просмотра всех возможных адресов и поступает на второй вход элемента ИЛИ 32, перебрасывается в нулевое состояние второй триггер 29, сигнал с которого поступает на третий вход второго элемента И 22 к запрещает прохождение импульсов с выхода генератора 27 на вход третьего счетчика 6„ С приходом следующего тактового импульса на объединенные тактовые входы регистров 17 и 18 сдвига, а ТЯКЖР на S-вход второго триггера 29 содержимое регистров 17 и 18 сдвига- ется на одну позицию вправо, а триггер 29 перебрасывается в единичное состояние, разрешая прохождение импульсов через второй элемент И 22 на вход третьего счетчика 26.

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

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

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

Приме р. Пусть в качестве блокового кода, которым кодируется группа неравномерных двоичных комбинаций, используется А Т, 12о код Хэмминга, исправляющий однократную ошибку. Для него , и для вышеприведенных (Фиг.З) обозначений Пусть передаче подлежат элементарные сообщения, кодируемые неравномерными комбинациями согласно приведенной таблице Для этой табли- Ч 1макс Ь, Тогда 1

log/ ваиия

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

ПХ2 4° Р2 АО-О,23 9,2 « 9;

пХ} 40-Р3 40-0,15 6;

пх 40-Р4 40-0,1 4;

п% 40-Р5 40-0,09 3,6 4;

пх 40.Р6 40-0,08 3,2 л 3;

пх 40-Р7 40 « 0,07 2,8 3;

nXg 40 Р8 40-0,03 1 ,.

Тогда общее число двоичных сигналов для кодирования данной совокупг. /макс

4 2 и , т „с для кодиро- i длины 1 отводится две позиции,

ности сообщений в соответствии с

таблицей будет равно 8

N

% пх.-п; « 102 + 9-2 + 6-3 + + + 4-4 + 3-4 + 3-4 + + Ь 4 112

В рассмотренном же кодеке для размещения неравномерных комбинаций отводится 118 позиций, значит, на оставшихся шести свободных позициях можно разметить еще определенное число комбинат ий, например х, и хэ, тогда и комбинация 1 будет имет значение 01„ При использовании же равномерных комбинаций в кодовом блоке можно закодировать только 40 элементарных сообщений, так как каждое из них содержит три двоичных посылки, а для размещения отводится 120 позиций Таким образом, при одинаковой достоверности (исправляется однократная ошибка) в рассмотренном кодеке передается на две комбинации больше„

Ф о

тения

рмула изобре

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

сть

й ерк, м, е

65138512

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

4Q информационным входом декодера, выходы блока коррекции ошибок соединены с установочными входами первого регистра сдвига, тактовый вход которого объединен с тактовым входом второго

45 регистра сдвига, первым входом .третьего элемента И, счетным входом второго счетчика импульсов и первым установочным входом второго триггера и является тактовым входом декодера, парал50 выходы первого регистра сдвига подключены к установочным входам первого счетчика импульсов, выход которого соединен с первым установочным входом первого триггера, выход

55 которого подключен к первым входам | первого и второго элементов И и вто- , рому входу третьего элемента И, выход которого соединен со счетным входом первого счетчика импульсов,

35

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

10

15

20

25

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

Фиг. 2

К

t г г Фиг.З

Т

20

LriTkt

п