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

:0 ц 9 ИЗО ТЕНИЯ САН К рственныи универитке ство. СССР 3/ОО, 1989. го кода с исправлениага счим вых На фиг, 1 и 2соответственно ккодера, входящидек; на фиг, 3построения кодов ОСУДАРСТВЕННЫЙ КОМИТЕТО ИЗОБРЕТЕНИЯМ И ОТКРЫТИРИ ГКНТ СССР РСКОМУ СВИДЕТЕЛЬСТ(56) Авторское свидетелМ 1651385, кл. Н 03 М 1 Изобретение относится к технике связии вычислительной технике и мажет быть использовано в системах передачи дискретной информации.Известен памехоустойчивый кодек дляпередачи дискретных сообщений, содержа.- щий кодер и декодер, кодер содержит первый и второй блоки постоянной памяти, первый и второй регистры сдвига, формирователь проверочных символов, делитель частоты, триггер, формирователь импульсов, первый и второй счетчики импульсов, элемент И, источник постоянного кода, компаратор, декодер содержит блок коррекции ошибок, первый и второй регистры сдвига, первый и второй блоки постоянной памяти, первый-третий элементы И, первый-третий счетчики импульсов, генератор импульсов, первый и второй триггеры, компаратор, дешифратор и элемент ИЛИ.Недостатком этого устройства являетсяснижение помехоустойчивости при возникновении ошибок, кратность которых больше корректирующей способности используе(54) ПОМЕХОУСТОЙЧИВЫЙ КОДЕК ДЛЯПЕРЕДАЧИ ДИСКРЕТНЫХ СООБЩЕНИЙ(57) Изобретение относится к технике связии вычислительной технике и может быть использовано в системах передачи дискретной информации. Цель изобретенияповышение помехоустойчивости кодека,Для этого в декодер дополнительно введены четвертый элемент И, третий триггер иинвертор с соответствующими функциональными связями. 3 ил,мого помехаустаичив ем ошибок,Целью иэабрете ние помехаустайчивЦель достигается мехоустойчиваго код ретных сообщений элемент И, третий тр которого подключен. и выход которого са дом четвертого эле которого подключен чика импульсов, а в рым установочны триггера, первый вхо к выходу втор этом решающ ся выход третьего тр ия является повыше- ости.тем, что в декодер поека.для передачи дисквведены четвертый иггер и инвертар, вход к выходу кампаратора единен со вторым вхамента И, первый вход к выходу переога счегыход соединен со вам входом третьего д которого подключен етчика импульсов, при одом декодера являетиггера. изображены блок-схемы одера и предлагаемого дс х в памехоустойчивый кс иллюстрирует принцис ого слова.Кодер содержит первый и второй блоки1, 2 постоянной памяти, первый и второйрегистры 3, 4 сдвига, формирователь 5 проверочных символов, делитель 6 частоты,триггер 7, формирователь 8 импульсов, первый и второй счетчики 9, 10 импульсов, элемент И 11, источник 12 постоянного кода икомпаратор 13, информационные входы 14и тактовый вход 15 кодера.Декодер содержит (фиг. 2) блок 16 коррекции ошибок, первый и второй регистры17, 18 сдвига, первый и второй блоки 19, 20постоянной памяти, первый - четвертый элементы И 21 - 23, 25, первый - третий счетчики24-26 импульсов, генератор 27 импульсов, 15первый-третий триггеры 28, 29, 36, компаратор 30, дешифратор 31, элемент ИЛИ 32и инвертор 37, информационный вход ЗЗ,тактовый вход 34 и решающий выход 38декодера, 20Блоки 1, 2, 19, 20 постоянной памятипредставляют собой ПЗУ.Формирователь 5 проверочных символов реализуется, например, на сумматорахпо модулю два в соответствии с применяемым помехоустойчивым кодом.Формирователь 8 импульсов выполненв виде ждущего мультивибратора.Блок 16 коррекции ошибок служит длядекодирования используемого помехоустойчивого кода с исправлением ошибок иможет быть реализован по известным схемам,В рассматриваемом кодеке элементарные дискретные сообщения кодируют неравномерными кодовыми комбинациями взависимости от априорных вероятностей ихпоявления: наиболее вероятные элементарные сообщения кодируют короткими последовательностями двоичных сигналов, аменее вероятные - длинными.Однако для определенного набора элементарных дискретных сообщений и их вероятностей существует ряд оптимальных 45кодов, имеющих одно и то же количестводвоичных сигналов, приходящихся на одноэлементарное сообщение, но обладающихразличной средней длиной распространения ошибок. 50Используя свойство размножения ошибок или неправильного разделения неравномерных кодовых комбинаций на приемепри возникновении ошибок в передаваемом кодовом блоке, возможно дополнительно обнаруживать некоторые ошибки скратностью, превышающей корректирующую способность применяемого помехоустойчивого кода. При этом количествообнаруживаемых ошибок и их кратность будут зависеть от структуры неравномерного кода, используемого для передачи дискрет. ных элементарных сообщений.Кодирование осуществляется по известному алгоритму, т,е. формируется блок фиксированной длины, содержащий и двоичных посылок (фиг. 3), из которых г являются проверочными, определяемыми в зависимости от значений посылок К и 1. В группу 1 входят 1 позиций, содерхащих неравномерные комбинации, подлежащие пеУредаче, и 6 свободных позиций от конца группы Мпеременной длины до начала группы 8. Х принимает значения 0,1,2, Яп), где Ьах - максимальная длина неравномерной кодовой комбинации. Служебная группафиксированной длины 1 = 1092 йпах представляет собой двоичное число, отображающее длину 1.в количестве двоичных посылок, и определяет местоположение конца группы 1, т.е. плавающую от блока к блоку границу с.Декодирование информации на приеме производится следующим образом.Декодирование принятого кодового блока из и двоичных посылок сначала производится как Ап, кода, т.е, по значениям позиций групп (М+) и г вычисляются контрольные суммы, составляющие синдром, Если синдром не равен нулю, то по его значению определяется местоположение одной или нескольких ошибочно принятых посылок из и, которые затем исправляются, После исправления ошибок в соответствии со служебной комбинацией 8 определяется местоположение плавающей границы 1, т.е. определяется длина группы 1, которая затем последовательно подразделяется на ряд неравномерных комбинаций, соответствующих совокупности элементарных сообщений, введенных на передаче.При возникновении ошибок большей кратности, чем имеющаяся корректирующая способность кода, исправляющего ошибки, местоположение ошибочно принятых посылок из и по вычисленным контрольным суммам определяется неверно и исправляются не порахенные ошибками, а правильные посылки. В результате этого вносятся дополнительные ошибки в принятый кодовый блок. При декодировании, начиная с определенной позиции группы Е, разделение неравномерных кодовых комбинаций осуществляется неверно вплоть до последней посылки 1. На основе анализа последней неравномерной кодовой комби-. нации, в случае ненахождения ей эквивалентной среди всех известных получателю информации неравномерных комбинаций, на выход декодера выдается решение об ошибочно принятом кодовом блоке. Затемпроисходит или просто стирание ошибочного кодового блока, или, в случае наличия системы с решающей обратной связью и ожиданием решающего сигнала, бсуществляется Стирание принятого блока и формирование сигнала переспроса, который по обратному каналу передается в передатчик.Кодек работает следующим образом, В кодере со входов 14 на адресные входы первого и второго блоков 1,2 постоянной памяти поступают дискретные сообщения в виде равномерных двоичных комбинаций, По переднему фронту импульса, приходящего с выхода делителя 6, коэффициент деления которого равен числу двоичных разрядов, соответствующих неравномерной кодовой комбинации максимальной длины, из первого блока 1 разрешается вы-.борка соответствующей неравномерной кодовой комбинации, а из второго блока 2 - 2 слова. содержащего двоичную запись длины этой комбинации, По заднему фронту этого же импульса, поступающего на входы разрешения параллельной загрузки регистра 3 и счетчика 9, информация, выбранная 2 из блоков 1 и 2, подается на параллельные входы первого регистра 3 сдвига и первого счетчика 9.импульсов и записывается в них.С приходом этого же импульса на Я-вход триггера 7 последний устанавливается в 3 единичное состояние и разрешает запуск формирователя 8 тактовыми импульсами, приходящими со входа 15 через открытый по второму входу элемент И 11. Импульсы с выхода фоомиоователя 8 постчпают на 3 тактовый вход первого счетчика 9, который работает нэ уменьшение счета, и на тактовые входы первого 3 и второго 4 регистров сдвига, осуществляя сдвиг неравномерной кодовой комбинации из регистра 3 в ре гистр 4 на определенное число разрядов, записанное в двоичном коде в первом счетчике 9, После обнуления счетчика 9 перепад логического уровня с выхода окончания счета этого счетчика поступает на Б-вход триг гера 7, переключая его в нулевое состояние и останавливая тем самым запуск формирователя 8 очередным тактовым импульсом, приходящим со входа 15. Неравномерная кодовая комбинация оказывается записан ной во втором регистре 4; Триггер 7, форми.- рователь 8, первый счетчик 9 с заведенной с его выхода обратной связью представляют собой программируемый генератор импульсов, выдающий заданное, записанное в 5 , двоичном коде в счетчик 9 количество импульсов, соответствующее числу разрядов каждой неравномерной кодовой комбинации.Таким образом, комбинации, выбранные из первого блока 1 постоянной памяти,последовательно записываются во второй регистр 4, накапливаясь в нем.Импульсы с выхода формирователя 8поступают также натактовый вход второго 5 счетчика 10, представляющего собой реверсивный счетчик, работающий на уменьшение счета, в котором первоначально из блока 12 записывается значение К, соответствующее общему числу свободных позиций 10 для информационных посылок. Двоичныйкод с выходов счетчика 10, соответствующий числу 1 оставшихся незанятыми позиций информационной части кодового слова, поступает на вторые входы цифрового ком паратора 13, на первые входы которого извторого блока 2 постоянной памяти поступает двоичный код, соответствующий числу позиций, занимаемых очередной передаваемой неравномерной кодовой комбина цией. В компараторе 13 происходитсравнение этих двух двоичных чисел. Если число оставшихся свободными позиций формируемого блока больше или равно числу позиций, занимаемых очередной кодовой 5 комбинацией, выбранной из первого блока1, то присутствующий на выходе компаратора 13 логический уровень, поступающий на второй вход элемента И. 11, разрешает запуск формирователя 8 тактовыми импульса- О ми, приходящими на его тактовый вход, иочередная неравномерная кодовая комбинация будет поразрядно записываться во второй регистр 4 сдвига, где происходит формирование передаваемого кодового 5 блока. Как только число свободных Юпозиций окажется меньше числа позиций очередной кодовой комбинации, на выходе компаратора 13 появится логический сигнал, запрещающий запуск формирователя 0 8, Этот же логический сигнал поступает навход разрешения параллельной загрузки регистра 4 сдвига и на управляющий вход формирователя 5 проверочных символов и разрешает запись с выходов счетчика .10 5 двоичного кода, соответствующего числу оставшихся незанятымипозиций кодовогоРслова, в отведенные для этой цели 1 позиций, а также разрешает формирование проверочных посылок и запись их в 0 соответствующие позиции регистра 4. Сигнал с выхода компаратора 13 поступает также нэ вход разрешения параллельной загрузки счетчика 10 и разрешает запись первоначального значения К позиций ин формационной части кодового слова от источника 12 постоянного кода в этот счетчик 10. Двоичный код, соответствующий числу 1 с, . появится на выходах счетчика 10, а, значит, и на вторых входах компарэтора 13., на первых входах которого будет присутствоватьдвоичный код, соответствующий числу позиций очередной подлежащей передаче кодовой комбинации.В результате сравнения на выходе компаратора 13 произойдет смена логического сигнала, что разрешит прохождение тактовых импульсов через элемент И 11, запускающих формирователь 8, который сдвигает записанную в регистре 3 очередную кодовую комбинацию и поразрядно записывает ее в регистр 4, из которого одновременно с записью происходит поразрядная выдача посылок сформированного прежде кодового блока. Таким образом, процесс формирования и выдача в канал связи (не показан) информации будут проходить одновременно, без задержки времени. Далее периодически формируются последующие кодовые блоки из и символов,В декодере кодовый блок из канала связи через вход 33 последовательно поступает на вход блока 16 коррекции ошибок, в котором происходит вычисление контрольных сумм составляющих синдрома. В случае, когда значение синдрома отлично от нуля, по его значению в блоке 16 коррекции происходит определение местоположения ошибочно принятых информационных посылок и их замена на правильные, В случае, когда количество пораженных ошибками посылок превышает корректирующую способность помехоустойчивого кода, их исправление происходит неверно, необнаруженные ошибки остаются и могут вноситься дополнительные ошибки в информационную часть кодового блока,Тактовые импульсы, частота следования которых подбирается так, чтобы в момент полной записи принятого кодового блока в блок 16 полностью очистился регистр 17 сдвига длиной в и-г ячеек, поступают со входа 34 на тактовый вход счетчика 25 и на объединенные тактовые входы регистров 17 и 18 сдвига, длина которого выбирается равной максимальному числу позиций, занимаемых неравнОмерной кодовой комбинацией, и осуществляют сдвиг и-г информационных посылок, переписываемых каждый раз в.регистр 17 из блока 16 после получения нового кодового слова.Таким образом, после полного заполнения счетчика 25, коэффициент пересчета которого также равен п-г, на его выходе появляется логический сигнал, поступающий на управляющий вход блока 16 коррекции и на входы разрешения параллельной загрузки регистра 17 сдвига и счетчика 24. а также на Я-вход триггера 35, разрешая параллельную запись из блока 16 информационных и - г посылок в регистр 17, а из10 15 емых принятыми неравномерными кодовы 20 25 40 45 50 55 30 35 соответствующих 4 позиций регистра 17 - двоичного кода. соответствующего длине. служебной группы гф, в счетчик 24 и устанавливая триггер 35 в единичное состояние, определяющее изначальное отсутствие необнаруженных ошибок в информационной части принятого кодового блока. Счетчик 24, представляющий собой двоичный счетчик с предварительной записью, коэффициент пересчета которого выбирается равным 3 с, подсчитывает число тактовых импульсов, поступающих со входа 34 на его вход через открытый по второму входу третий элемент И 23 и определяет число Ьпозиций, занимами комбинациями, входящими в данный кодовый блок, а значит, и плавающую границу с для этого блока; После полного заполнения счетчика 24 на его выходе появляется логический сигнал, поступающий на В-вход первого триггера 28 и перебрасывающий его в нулевое состояние, запрещая тем самым прохождение тактовых импульсов на вход счетчика 24 через элемент И 23. Этот же логический сигнал с выхода триггера 28 поступает на второй вход первого элемента И 21 и запрещает последовательное поступление во второй регистр 18 оставшихся записанными в первом регистре 17 служебных групп посылок 4 и 1, Соответствующие выходы второго регистра 18 соединены параллельно с адресными входами первого блока 19 постоянной памяти и с первыми входами цифрового компаратора 30. Тактовые импульсы, поступающие на Я-вход второго триггера 29, устанавливают его каждый раз в единичное состояние, разрешая тем самым прохождение импульсов с выхода генератора 27 .через второй элемент И 22,открытый по первому входу логическим сигналом с выхода первого триггера 28, Эти импульсы с генератора 27 начинают проходить с момента начала поразрядного поступления неравномерных кодовых комбинаций очередного принятого блока во второй регистр 18. Импульсы с выхода генератора 27, частота которого выбирается больше частоты следования тактовых импульсов в число раз, равное числу всевозможных неравномерных кодовых комбинаций, соответствующих алфавиту источника сообщения, подсчитываются третьим счетчиком 26, на выходах которого формируется адрес; параллельно поступающий на соответствующие адресны входы второго блока 20 постоянной памяти и на вторые входы компаратора 30,В результате сравнения кодовой комбинации, поразрядно записываемой вп второй регистр 18 сдвига, с выбираемыми из оторокодовых комбинаций в компараторе 30 по-. 40вторяется снова и завершится. после поразрядного прохождения через второй регистр -. 18 всех информационных посылок группы К, поступающих из первого регистра 17 сдвига, до тех пор, пока не заполнится счетчик 45 24 и не перебросит первый триггер 28 в нулевое состояние, запрещая прохождение информационных посылок по второму входу первого элемента И 21 на вход регистра 18.При возникновении в принятом блоке инфор мации большего числа ошибок, чем корректирующая способность помехоустойчивого кода, разделение на неравномерные кодовые комбинации и их декодирование осуществляетсяневерно, Тогда, в ряде подобных случаев, после записи последней информационной посылки в регистр 18 сдвига и просмотра всех возможных неравномерных кодовых комбинаций, записанных во втором блоке 20 посто" янной памяти по всем адресам,го блока 20 постоянной памяти известными получателю неравномерными кодовыми комбинациями источника, при совпадении двух комбинаций, поступающих на соответ. ствующие входы компаратора 30, на его выходе появляется логический сигнал, приходящий на вход разрешения выборки первого блока 19, разрешая выдачу первичной информации, хранящейся в этом. блоке 19 и соответствующей данной неравномерной кодовой комбинации, т,е. происходит разделение информационных посылок на неравномерные кодовые комбинации, Кроме того, этим же логическим сигналом с выхода компаратора 30, поступающим на первый вход элемента ИЛИ 32 или же (в случае ненахождения кодовой комбинации, эквивалентной записанной в этот момент во втором регистре 18) сигналом с выхода дешифратора 31, который появляется после заполнения счетчика 26 и просмотра всех возможных адресов и поступает на второй вход элемента ИЛИ 32, перебрасывается в нулевое состояние второй триггер 29, сигнал с которого поступает на третий вход второго элемента И 22 и запрещает прохождение импульсов с выхода генератора 27 на .вход третьего счетчика 26, С приходом следующего тактового импульса на обьединенные тактовые входы регистров 17, 18 сдвига, а также на Я - вход второготриггера 29 содержимое оегистров 17, 18 сдвигается на одну позицию вправо, а тригер 29 перебрасывается в единичное состояние, разрешая прохождение импульсов через второй элементИ 22 на вход третьего счетчика 26; Таким образом, процесс формирования адресов счетчиком 26, просмотр содержимого второго блока 20 постоянной памяти и сравнение 5 10 15 20253035 формируемым счетчиком 26, кодовая комбинация, эквивалентная записанной в регистре 18, не находится. На выходедешифратора 31 происходит смена логического сигнала, а на выходе компаратора 30логический сигнал не изменяется и подается на вход инвертора 37. Инвертированныйв блоке 37 сигнал поступает на второй входчетвертого элемента И 35, на первом входекоторого после полного заполнения счетчика 24 появляется логический сигнал, определяющий окончание декодирования группык, т.е. границутдля данного блока. Сменалогического сигнала на выходе элемента И35, поступающего на В-вход третьего триггера 36, устанавливает его в нулевое состояние, Соответствующий логический сигналпоявляется на решающем выходе 38 декодера, определяя наличие ошибок в принятомкодовом блоке. Тогда данный блок или стирается, или может подаваться запрос на повторную передачу этого блока,В случае, если число ошибок в принятомкодовом блоке соответствует корректирующей способности помехоустойчивого кода,или же, когда ошибки большей кратностисоздают такое разделение на неравномерные кодовые комбинации, что последняя посылка, записываемая в регистр 18, приводитк разрешенной кодовой комбинации, которой соответствует эквивалентная комбинация из блока 20, на выходе компаратора 30не происходит смена логического сигнала итриггер 36 остается в единичном состоянии,т.е, принятый кодовый блок является безошибочным или в нем присутствуют необнарукенные ошибки, На решающем выходе 38декодера остается прежний логический сигнал,Следующий цикл обработки нового кодового блока, поступающего на вход 33 де-кодера, начнется после заполнениясчетчика 25, выдачи им нового сигнала раэ.решения и установки триггера 36 в единичн ое состоя н и е.Рассмотрим конкретный пример, Пустьсимволам источника соответствуют. неравномерные кодовые комбинации, показанные в таблице.В качестве помехоустойчивого кода используется код Хэмминга А 1 Б.11, исправляющийоднократную ошибку. Предположим, что пе-р.едаче подлежит последовательностьАВС Тогда сформированный кодовыйблок в соответствии с кодом А 1 у 1 и приведенной таблицей, будет выглядеть следующим образом: С С 1 С 010 Св 0110001,гдеС 1, Сг, Сд, Са- проверочные символы, определяемые по следующим формулам:С 1= СзЭС 5+)С 78 С 90+С 1 гЯС 15,1727201 35 С 2 = СЗО+С 69 С 7 С 109 С 1 ЗС 14 Ж С 15, С 4 = С 5 Э С 69 С 78 С 12 З С 139 С 14 С 15, С 8 = С 9 ЬС 109 С 11 О+С 129 С 13 ЙС 149 С 15; и где Сз = 1, С 5 = О, С 6 = 1, С 7-0, С 9-О, С 1 оф -1,С 11= г, С 12=0, 5Так как длина к равна 8 двоичным по-. сылкам, тогда М и г определяются соответственно как: С 1 з - О, С 14 = О, С 15 = 1, Предположим, что в кодовом блоке после передачи в канал связи произошла двукрат ная ошибка и инвертировались третья и девятая посылки (т.е. Сз - 1, С 9 = 1). Тогда на приеме вычисленный синдром 41 будет иметь вид: 343 з 3231 = 0101, После исправления ошибок и инверсии десятого разряда 15 информационная часть М принятого кодового блока (без учета комбинаций Фи Ю) будет разделяться на неравномерные комбинации следующим образом: 00 1 ОО 1 1 1 О. Последняя кодовая комбинация, получен ная в результате такого (неправильного) разделения, не соответствует ни одной из записанных в блоке 20 постоянной памяти неравномерных кодовых комбинаций. Это означает, что в принятом кодовом блоке 25 произошло более одной ошибки, и декодером получателю информации выдается сообщение об ошибочном блоке.Таким образом, преимущество предлагаемого кодека заключается в повышении 30 помехоустойчивости при передаче дискретных сообщений эа счет дополнительного об-. наружения ошибок, кратность которых превышает корректирующую способность используемого помехоустойчивого кода, При этом эффект достигается без введения дополнительных проверочных символов в кодовый блок за счет использования свойства размножения ошибок при декодировании неравномерных кодовых комбинаций. Формула изобретения Помехоустойчивый кодек для передачи дискретных сообщений по авт,св. %1651385,отличающийся тем,что,с целью повышения помехоустойчивости кодека, в декодер введены четвертый элемент И, третий триггер и инвертор. вход и выход которого подключены соответственно к выходу компаратора. и первому входу четвертого элемента И, второй вход которого подключен к выходу первого счетчика импульсов, первый и второй установочные входы третьего триггера подключены соответственно к выходу второго счетчика импульсов и выходу четвертого элемента И, решающим выходом декодера является выход третьего триггера.