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

 

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

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

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

РЕСПУБЛИК

p0 ling g

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

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

ПРИ ГКНТ СССР

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

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (61) 1651385 (21) 4851062/24 (22) 10.07.90 (46) 15.04.92. Бюл. М 14 (71) Гродненский государственный университет (72). Б.А.Ассанович и Т,А.Ситкевич (53) 621.394.14 (088.8) (56) Авторское свидетельство. СССР

М 1651385, кл. Н 03 M 13/00, 1989.

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

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

Недостатком этого устройства является снижение помехоустойчивости при возникновении ошибок, кратность которых больше корректирующей способности используеSU 1727201 А2 (54) ПОМЕХОУСТОЙЧИВЫЙ КОДЕК ДЛЯ

ПЕРЕДАЧИ ДИСКРЕТНЫХ СООБЩЕНИЙ (57) Изобретение относится к технике связи и вычислительной технике и может быть использовано в системах передачи дискретной информации. Цель изобретения повышение помехоустойчивости кодека, Для этого в декодер дополнительно введены четвертый элемент И, третий триггер и инвертор с соответствующими функциональными связями. 3 ил, мого помехоустойчивого кода с исправлением ошибок.

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

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

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

1727? 01

Кодер содержит первый и второй блоки

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

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

17, 18 сдвига, первый и второй блоки 19, 20 постоянной памяти, первый — четвертый weменты И 21 — 23, 25, первый — третий счетчики

24-26 импульсов, генератор 27 импульсов, 15 первый-третий триггеры 28, 29, 36, компаратор 30, дешифратор 31, элемент ИЛИ 32 и инвертор 37, информационный вход 33, тактовый вход 34 и решающий выход 38 декодера. 20

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

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

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

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

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

Однако для определенного набора элементарных дискретных сообщений и их вероятностей существует ряд оптимальных 45 кодов, имеющих одно и то же количество двоичных сигналов, приходящихся на одно элементарное сообщение, но обладающих различной средней длиной распространения ошибок. 50

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

Кодирование осуществляется по известному алгоритму, т.е. формируется блок фиксированной длины, содержащий и двоичных посылок (фиг. 3), из которых г являются проверочными, определяемыми в зависимости от значений посылок k u l. В группу k входят 1 позиций, содер>кащих неравномерные комбинации, подлежащие пе/ редаче, и 6 свободных позиций от конца группы k ïåðåìåííîé длины до начала группы f. Х принимает значения 0,1,2, (lm x-1), где trna>< — максимальная длина неравномерной кодовой комбинации. Служебная группа (фиксированной длины 4 = fogzfmax представляет собой двоичное число, отображающее длину 1 .в количестве двоичных посылок, и определяет местоположение конца группы k, т.е. плавающую от блока к блоку границу с.

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

Декодирование принятого кодового блока из и двоичных flocblRQK сначала производится как Ап, < кода, т.е. по значениям позиций групп (1+ ) и r вычисляются контрольные суммы, составляющие синдром.

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

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

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

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

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

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

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

Импульсы с выхода формирователя 8 поступают также на тактовый вход второго

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

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

5 комбинацией, выбранной из первого блока

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

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

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

5 двоичного кода, соответствующего числу оставшихся незанятыми (позиций кодового

/ слова, в отведенные для этой цели t позиций, а также разрешает формирование проверочных посылок и запись их в

0 соответствующие позиции регистра 4. Сигнал с выхода компаратора 13 поступает также нэ рход разрешения параллельной загрузки счетчика 10 и разрешает запись первоначального значения k позиций ин5 формационной части кодового слова от источника 12 постоянного кода в этот счетчик

10. Двоичный код, соответствующий числу k, . появится на выходах счетчика 10, а, значит, и на вторых входах компарэтора 13., на первых входах которого будет присутствовать

1727201 двоичный код, соответствующий числу позиций очередной подлежащей передаче кодовой комбинации.

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

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

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

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

15 емых принятыми неравномерными кодовы20

40

50

35 соответствующих 4 позиций регистра 17— двоичного кода. соответствующего длине. служебной группы t, в счетчик 24 и устанавливая триггер 35 в единичное состояние, определяющее изначальное отсутствие необнаруженных ошибок в информационной части принятого кодового блока. Счетчик 24, представляющий собой двоичный счетчик с предварительной записью, коэффициент пересчета которого выбирается равным К подсчитывает число тактовых импульсов, поступающих со входа 34 íà его вход через открытый по второму входу третий элемент

И 23 и определяет число k ïîçèöèé, занимами комбинациями, входящими в данный кодовый блок, а значит, и плавающую границу с для этого блока; После полного заполнения счетчика 24 на его выходе появляется логический сигнал, поступающий на R-вход первого триггера 28 и перебрасывающий его в нулевое состояние, запрещая тем самым прохождение тактовых импульсов на вход счетчика 24 через элемент И 23. Этот же логический сигнал с выхода триггера 28 поступает на второй вход первого элемента

И 21 и запрещает последовательное поступление во второй регистр 18 оставшихся записанными в первом регистре 17 служебных групп посылок4 и 1 . Соответствующие выходы второго регистра 18 соединены параллельно с адресными входами первого блока

19 постоянной памяти и с первыми входами цифрового компаратора 30. Тактовые импульсы, поступающие на $-вход второго триггера 29, устанавливают его каждый раз в единичное состояние, разрешая тем самым прохождение импульсов с выхода генератора 27 .через второй элемент И 22, открытый по первому входу логическим сигналом с выхода первого триггера 28. Эти импульсы с генератора 27 начинают проходить с момента начала поразрядного поступления неравномерных кодовых комбинаций очередного принятого блока во второй регистр 18. Импульсы с выхода генератора 27, частота которого выбирается больше частоты следования тактовых импульсов в число раз, равное числу всевозможных неравномерных кодовых комбинаций, соответствующих алфавиту источника сообщения, подсчитываются третьим счетчиком 26, на выходах которого формируется адрес; параллельно поступающий на соответствующие адресны» входы второго блока 20 постоянной памяти и на вторые входы компаратора 30.

В результате сравнения кодовой комбинации, поразрядно записываемой on второй регистр 18 сдвига, с выбираемыми из оторо1.72 7201

10 кодовых комбинаций в компараторе 30 по-. 40 вторяется снова и завершится. после поразрядного прохождения через второй регистр

-. 18 всех информационных посылок группы k, поступающих из первого регистра 17 сдвига, до тех пор, пока не заполнится счетчик 45

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

При возникновении в принятом блоке инфор- 50 мации большего числа ошибок, чем корректирующая способность помехоустойчивого кода, разделение на неравномерные кодовые комбинации и их декодирование осуществляется неверно. Тогда, в ряде подобных случаев, после записи последней информационной посылки в регистр 18 сдвига и просмотра всех возможных неравномерных кодовых комбинаций, записанных во втором блоке 20 посто" янной памяти по всем адресам, го блока 20 постоянной памяти известными получателю неравномерными кодовыми комбинациями источника, при совпадении двух комбинаций, поступающих на соответствующие входы компаратора 30, на его выходе появляется логический сигнал, приходящий на вход разрешения выборки первого блока 19, разрешая выдачу первичной информации, хранящейся в этом. блоке

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

И 22 на вход третьего счетчика 26; Таким образом. процесс формирования адресов счетчиком 26, просмотр содержимого второго блока 20 постоянной памяти и сравнение

35 формируемым счетчиком 26, кодовая комбинация, эквивалентная записанной в регистре 18, не находится. На выходе дешифратора 31 происходит смена логического сигнала, а на выходе компаратора 30 логический сигнал не изменяется и подается на вход инвертора 37. Инвертированный в блоке 37 сигнал поступает на второй вход четвертого элемента И 35, на первом входе которого после полного заполнения счетчика 24 появляется логический сигнал, опреде ляющий окончание декодирования группы

k, т.е. границу т для данного блока. Смена логического сигнала на выходе элемента И

35, поступающего íà R-вход третьего триггера 36, устанавливает его в нулевое состояние. Соответствующий логический сигнал появляется на решающем выходе38декодера, определяя наличие ошибок в принятом кодовом блоке. Тогда данный блок или стирается, или может подаваться запрос на повторную передачу этого блока.

В случае, если число ошибок в принятом кодовом блоке соответствует корректирующей способности помехоустойчивого кода, или же, когда ошибки большей кратности создают такое разделение на неравномерные кодовые комбинации, что последняя посылка, записываемая в регистр 18, приводит к разрешенной кодовой комбинации, которой соответствует эквивалентная комбинация из блока 20, на выходе компаратора 30 не происходит смена логического сигнала и триггер 36 остается в единичном состоянии, т.е, принятый кодовый блок является безошибочным или в нем присутствуют необнару>кенные ошибки, На решающем выходе 38 декодера остается прежний логический сигнал, Следующий цикл обработки нового кодового блока, поступающего на вход 33 де- кодера, начнется после заполнения счетчика 25, выдачи им нового сигнала разрешения и установки триггера 36 в единичн ое состоя н и е.

Рассмотрим конкретный пример. Пусть символам источника соответствуют. неравномерные кодовые комбинации, показанные в таблице.

В качестве помехоустойчивого кода используется код Хэмминга А15,11, исправляющий однократную ошибку. Предположим, что передаче подлежит последовательность

АВС.... Тогда сформированный кодовый блок в соответствии с кодом А 1,11 и приведенной таблицей, будет выглядеть следующим образом: С С в1 С 010Са0110001,где

С1, Сг. С4, Са- проверочные символы, определяемые по следующим формулам:

С = СзЭСь(+)СтвС90+С1г ЯС1ь, 1727201

C2 = СЗО+С69 С7P С10ф С11ъ ЬС148 С15, С4 = С5Э С58 С7Э С12З С 139 С14®С15, C8 = C9(3C10®C»O+C 129 С13® С149 С15; и где Сз = 1, С5 = О, С5 = 1, С7- О, Cg - О, С 10

-1,C»= г, С1г=О, 5

Так как длина k равна 8 двоичным по-. сылкам, тогда 1 и г определяются соответственно как: С13 - О, С14 = О, С15 = 1.

Предположим, что в кодовом блоке после передачи в канал связи произошла двукрат- 10 ная ошибка и инвертировались третья и девятая посылки (т.е. Сз - 1, Cg =. 1). Тогда на приеме вычисленный синдром (4) будет иметь вид: $4$з$г$1 = 0101. После исправления ошибок и инверсии десятого разряда 15 информационная часть k принятого кодового блока (без учета комбинаций Фи Ю ) будет разделяться на неравномерные комбинации следующим образом: 00 1 00 1 1 1 О.

Последняя кодовая комбинация, получен- 20 ная в результате такого (неправильного) разделения, не соответствует ни одной из записанных в блоке 20 постоянной памяти неравномерных кодовых комбинаций. Это означает, что в принятом кодовом блоке 25 произошло более одной ошибки, и декодером получателю информации выдается сообщение об ошибочном блоке.

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

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

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

¹ 165 1385, отличающийся тем, что,. с целью повышения помехоустойчивости кодека, в декодер введены четвертый элемент И, третий триггер и инвертор, вход и выход которого подключены соответственно к выходу компаратора. и первому входу четвертого элемента И, второй вход которого подключен к выходу первого счетчика импульсов, первый и второй установочные входы третьего триггера подключены соответственно к выходу второго счетчика импульсов и выходу четвертого элемента И, решающим выходом декодера является выход третьего триггера.

1727203

1727201

1 727201

Составитель Б,Ассанович

Техред М.Моргентал Корректор Л.Патай

Редактор Н.Каменская

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

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

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

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