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

, Блоки 1, 2, 19 и 2 О постоянной памяти представляют собой ПЗУ.Формирователь 5 проверочных символов реализуется, например, на сумматорах по модулю два в соответствии с применяемым помехоустойчивым кодом.Формирователь 8 импульсов выполнен в виде ждущего мультивибратора.Блок 16 коррекции ошибок служит 1 О для декодирования используемого помехоустойчивого кода с исправлением ошибок и может быть реализован по известным схемам.В рассматриваемом кодеке элемен тарные дискретные сообщения предварительно кодируют неравномерными кодовыми комбинациями в зависимости от априорных вероятностей их появления: наиболее вероятные элементарные 2 О сообщения кодируют короткими после,довательностями двоичных сигналов, а менее вероятные - длинными.При построении такого неравномерного кода необходимо учесть требова ння однозначности декодирования. Для однозначности декодирования необходимо, чтобы ни одна кодовая комбинация меньшей длины не совпадала с началом кодовой комбинации большей ЗО длины, т.е. код должен обладать свойством неприводимости. В качестве при" .мера рассмотрим неравномерный двоичный код Шеннона-Фано. Соответствие неравномерных кодовых комбинаций 35 элементарным сообщениям источника с учетом априорной вероятности их появления Р; (х) показано в таблице.После такого кодирования формиру ется блок фиксированной длины, содержащей и двоичных посылок (фиг.З). Из и посылок г являются .проверочными, формируемыми в соответствии с выбранным блочным кодом. Значения этих г 45 посылок определяются в зависимости от значений посылок, входящих в группы К и 1. Группа К,составляется из совокупности неравномерных, кодовых комбинаций, соответствующих элементарным сообщениям, произвольным образом поступающим от источника и подлежащим передаче, поэтому из-за неравномерности этих кобинаций граница г является плавающей. Это значит, что в общем случае не все К позиций заполняются ннформационньпчи посылками, при поступлении очередной неравномерной комбинации при формировании кодового блока может оказаться, что свободное расстояние 1 меньше, чем длина этой комбинации. В этом4случае 1 позиций остаются свободными а поступившая неравномерная комбинация будет использована в качестве первой для формирования следующего кодового блока из и посылок. Из К посылок информационными будут являться К позиций. Для правильного/разделения неравномерных комбинаций на приеме и исключения вставок лишних комбинаций необходимо сформировать метку, определяющую местоположение конца группы К , т.е. плавающуюот блока к блоку границу С. Кодирование местоположения границы Г или( Ф то же самое длины группы 1 , производится с помощью служебнойгруппы 1 фиксированной длины, эта группа представляет собой двоичное число отобЭ ражающее длину группы 1 , выраженную в количестве двоичных посылок. Еслй1учесть, что 1 может принимать значения 0,1,2,ф(1 макс 1) ь где 1 макс максимальная длина неравномерных кодовых комбинаций, то длина 1 определяется как 11 о 81 макс, Итак, группы г и 1 имеют фиксированную длину, группа 1 - свободные позиции от конца группы К переменной длины до начала группы 1, значения посылок группы 1 есть двоичное число выражаюеЭ щее длину группы 1Декодирование информации на приеме производится следующим образом. Принятый кодовый блок из и двоичных посылок сначала декодируется как А ь к код, т.е. по значениям позиций групп (К+1) и г вычисляются контроль" ные суммы, составляющие синдром, Если синдром не равен нулю, то по его значению определяется местоположение одной или нескольких ошибочно принятых посылок из и, которые затем исправляются. После исправления ошибок в соответствии со служебной комбинацией 1 определяется местоположение плавающей границы С, т.е. определяется длина группы К , затем группа К разделяется на ряд неравномерных комбинаций, соответствующих совокупности элементарных сообщений, введенных на передаче.Кодек работает следующим образом.В кодере с входов 14 на адресные входы первого и второго блоков 1 и 2 постоянной памяти поступают днскрет.-.ные сообщения в виде равномерныхдвоичных комбинаций. По переднемуфронту импульса, приходящего с выходаделителя б, коэффициент деления которого равен числу двоичных разрядов,соответствующих неравномерной кодовойкомбинации максимальной длины, нзпервого блока 1 разрешается выборкасоответствующей неравномерной кодо"вой комбинации, а из второго блока2 - слова, содержащего двоичную запись длины этой комбинации. По зад-нему Фронту этого же импульса, поступающего на входы разрешения параллельной загрузки регистра 3 и счетчика9, информация, выбранная из блоков1 и 2, подается на гараллельные входы первого регистра 3 сдвига и первого счетчика 9 импульсов и записывается в них, С приходом этого же импульса на Я-вход триггера 7 послед-.ний устанавливается в единичное состояние и разрешает запуск .Формирователя 8 тактовыми импульсами, приходящими с входа 15 через открытый повторому входу элемент И 11. Импульсыс выхода формирователя 8 поступаютна тактовый вход первого счетчика9, который работает на уменьшениесчета, и на тактовые входы первого3 и второго 4 регистров сдвига, осуществляя сдвиг неравномерной кодовойкомбинации из регистра 3 в регистр 4на определенное число разрядов, записанное в двоичном коде в первомсчетчике 9. После Обнуления счетчика9 перепад логического уровня с выхода окончания счета этого счетчикапоступает на К-вход триггера 7, переключая его в нулевое состояние иостанавливая тем самым запуск Формирователя 8 очередным тактовым импульсом, приходящим с входа 15, Неравномерная кодовая комбинация оказывается записанной во втором регистре 4.Триггер 7, формирователь 8, первыйсчетчик 9 с заведенной с его выходаобратной связью представляют собойпрограммируемый генератор импульсов,выдающий заданное, записанное в двоичном коде в счетчик 9 количество импульсов, соответствующее числу.разрядов каждой неравномерной кодовойкомбинации. Таким образом, комбинации, выбранные из первого блока 1 постоянной памяти, последовательно записываются40 45 50 55 Как только число свободных 1 позиций окажется меньше числа позиций очередной кодовой комбинации, на выходе компаратора 13 появится логический сигнал, запрещающий запуск формирователя 8. Этот же логический сигнал поступает на вход разрешения параллельной загрузки регистра 4 сдвига и на управляющий вход формирователя 5 проверочных символов и разрешает запись с выходов счетчика 10 двоичного кода, соответствующего числу оставшихся незанятыми 1 позиций кодового слова, в отведенные для этой цели 1 позиций, а также разрешает формирование проверочных посылок и запись их в соответствующие г позиций регистра 4. Сигнал с выхода компаратора 1 3 поступает также во второй регистр 4, накапливаясь внем.Импульсы с выхода Формирователя 8 5поступают также на тактовый входвторого счетчика 10, представляющегособой реверсивный счетчик, работающий на уменьшение счета, в которомпервоначально из блока 12 записывается значение К, соответствующее общему числу свободных позиций для информационных посылок. Двоичный код с выходов счетчика О, соответствующийчислу 1 оставшихся незанятыми позиций информационной части кодового1слова, поступает на вторые входы цифрового компаратора 13, на первые входы которого из второго блока 2 постоянной памяти поступает двоичный 20 код, соответствующий числу позиций,занимаемых очередной передаваемой неравномерной кодовой комбинацией. Вкомпараторе 13 происходит сравнениеэтих двух двоичных чисел. Если число425 1 оставшихся свободными позицийформируемого блока больше или равночислу позиций, занимаемых очереднойкодовой комбинацией, выбранной изпервого блока 1, то присутствующий 30 на выходе компагатора 13 логическийуровень, поступающий на второй входэлемента И 11, разрешает запуск формирователя 8 тактовыми импульсами,приходящими на его тактовый вход,и Очередная неравнОмерняя кодоваякомбинация будет поразрядно загисываться во второй регистр 4 сдвига,где происходит формирование передаваемого кодового блока.20 на вход разрешения параллельной загрузки счетчика 10 и разрешает запись первоначального значения К позиций информационной части кодового слова от источника 12 постоянного кода в этот счетчик 10. Двоичный код, соответствующий числу К, появится на вы/ходах счетчика 10, а значит, и на вторых, входах компаратора 1 3, на 1 О первых входах которого будет присутствовать двоичный код, соответствующий числу позиций очередной подлежащей передаче кодовой комбинации.В результате сравнения на выходе 15 компаратора 13 произойдет смена логического сигнала, что разрешит прохождение тактовых импульсов через элемент И 11, запускающих формирователь 8, который сдвигает записанную в регистре 3 очередную кодовую комбинацию и поразрядно.-записывает ее в регистр 4, из которого одновременно с записью происходит поразрядная выдача посылок сформированного прежде кодового блока, Таким образом, процесс формирования и выдача в канал связи (не показан) информации будут проходить одновременно, без задержки времени, Далее периодичес ки Формируются последующие кодовые блоки из и символов.В декодере кодовый блок из канала связи через вход 33 последовательно поступает на вход блока 16 коррекции ошибок, в котором происходит вычисление контрольных сумм составляющих синдрома. В случае, когда значение синдрома отлично от нуля, по его значению в блоке 1 6 коррекции пронсхо дит определение местоположения ошибочно принятых информационных посылок и их замена на правильные.Тактовые импульсы, частота следования которых подбирается так, чтобы 45 в момент полной записи принятого кодового блока в блок 16 полностью очистился регистр 17 сдвига длиной в и-т ячеек, поступают с входа 34 на тактовый вход счетчика 25 н на 50объединенные тактовые входы регистров 17 и 18 сдвига, длина которого выбирается равной максимальному числу позиций, занимаемых неравномернойкодовой комбинацией и осуществляют 55 сдвиг и-г информационных посылок, переписываемых каждый раз в регистр 17 из блока 16 после получения нового кодового слова. Таким образом, после полного заполнения счетчика 25, коэффициент пересчета которого также равен п-г, на его выходе появляется логический сигнал поступающий на управляющий вход блока 16 коррекции и на входы разрешения параллельной загрузки регистра 17 сдвига и счетчика 21, разрешая параллельную запись из блока 16 исправленных информационных и-г посыпок в регистр 17, а из соответствующих 1 позиций регистра 1 7 двоичного кода, соответствующего длине служебной группы 1 , - в счетчик 24.ОСчетчик 24, представляющий собой двоичный счетчик с предварительной записью, коэффициент пересчета которого выбирается равным К, подсчитыва.: ет число тактовых импульсов, поступающих с входа 34 на его вход через открытый по второму входу третий элемент И 23 и определяет число К понФзицни, занимаемых принятыми неравномерными кодовыми комбинациями, входящими в данный кодовый блок, а значит, и плавающую границу й для этого блока.После полного заполнения счетчика 24 на его выходе появляется логический сигнал, поступающий на В.-вход первого триггера 28 и перебрасывающий его в нулевое состояние, запрещая тем самым прохождение тактовых импульсов на вход счетчика 24 через элемент И 23. Этот же логический сигнал с выхода триггера 28 поступает на второй вход первого элемента И 21 и запрещает последовательное поступление во второй регистр 1 8 оставшихся записанными в первом регистре 1 7 служебных групп посылок 1 к 1". Соответствующие выходы второго регистра 1 8 соединены параллельно с адресными входами первого блока 19 постоянной памяти и с первыми входами цифрового компаратора 30. Тактовые импульсы, поступающие на Я-вход второго триггера 29, устанавливают его каждый раз в единичное состояние, разрешая тем самым прохождение импульсов с выхода генератора 27 через второй элемент И 22, открытый по первому входу логическим сигналом с выхода первого триггера 28. Эти импульсы с генератора 27 начинают проходить с момента начала поразрядного поступления неравномерных кодовых комбинаций очередного принятого блока во второй40 Ърегистр 18. Импульсы с выхода генератора 27, частота которого выбирается больше частоты следования тактовыхимпульсов в число раз, равное числувсевозможных неравномерных кодовыхкомбинаций, соответствующих алфавитуисточника сообщения, подсчитываютсятретьим счетчиком 26, на выходах которого формируется щрес, параллельно 10поступающий на соответствующие адресные входы второго блока 20 постоянной памяти и на вторые входы компаратора 30.В результате сравнения кодовой 15комбинации, поразрядно записываемойво второй регистр 18 сдвига, с выбираемыми из второго блока 20 известными получателю неравномерными кодовыми комбинапиями источника при совпадении двух комбинаций, поступающихна соответствующе входы компаратора30, на его выходе появляется логический сигнал, приходящий на вход разрешения выборки первого блока 19,разрешая выдачу первичной информации,хранящейся в этом блоке 19 и соответствующей данной неравномерной кодовойкомбинации. Кроме того, этим же логическим сигналом с выхода компаратора 3030, поступающим на первый вход элемента ИЛИ 32 или же (в случае ненахождения кодовой комбинации, эквивалентной записанной в этот момент во втором регистре 8) сигналом с выходадешифратора 31, который появляетсяпосле заполнения счетчика 26 и просмотра всех возможных адресов и поступает на второй вход элементаИЛИ 32, перебрасывается в нулевоесостояние второй триггер 29, сигналс которого поступает на третий входвторого элемента И 22 и запрещаетпрохождение импульсов с выхода генератора 27 на вход третьего счетчика 4526. С приходом следующего тактовогоимпульса на объединенные тактовыевходы регистров 17 и 18 сдвига, атякж на Я-вход второго триггера 29содержимое регистров 17 и 18 сдвигается на одну позицию вправо, а триггер 29 перебрасывается в единичноесостояние, разрешая прохождение импульсов через второй элемент И 22на вход третьего счетчика 26.55Таким образом, процесс формирования адресов счетчиком 26, просмотрсодержимого второго блока 20 постоян 1ной памяти и сравнение кодовых комбинаций в компараторе 30 повторяются снова и завершаются после поразрядного прохождения через второй регистр 18 всех информационных посылок групАпы К ,поступающих из первого регистоа 17 сдвига, до тех пор, пака не заполнится счетчик 24 и не перебросит первый триггер 28 в нулевое состояние, запрещая прохождение информационных посылок по второму входу первого элемента И 21 на вход регистра 18.Следующий цикл обработки нового кодового блока, поступающего на вход 33 декодера, начнется после заполнения счетчика 25 и выдачи им нового сигнала разрешения.Таким образом, процесс приема, т.е. записи кодового блока в блок 16 коррекции ошибок, и обработка предыдущего информационного блока происходит непрерывно.П р и м е р, Пусть в качестве блокового кода, которым кодируется группа неравномерных двоичных комбинаций, используется А 27 0 код Хэмминга, исправляющий однократную ошибку. Для него и 127, г=7 и для вышеприведенных (фиг.З) обозначений К+1=120. Пусть передаче подлежат элементарные сообщения, кодируемые неравномерными комбинациями согласно приведенной таблице. Для этой таблицы 1 макс=4. Тогда 1 = 1 о 8 г 1 макс = 1 оя 4 = 2 и К=118, те. для кодирования длины 1 отводится две позиции, а для размещения неравномерных инфор- мационных комбинаций - 118. Предположим, что от источника на передаче поступают 40 элементарных сообщений, в соответствии с вероятностями Р, (рассмотрим типичный случай, который имеет место в среднем) количество конкретных сообщений п, будет равнои = 40 Р = 40 0,25 = 10;и 40 Р 40 О 23 9 2 91и), -- 40 Рз = 400,15 = 6;и = 40 Р = 40 0 1 = 4;хфи = 40 Р = 40 0 09 = 3 64Х 5ф э в40 Р 6 40б40 Рт 40 0,07 2 8 31и = 40 Р 8 = 400,03 = 1,2-"1,Тогда общее число двоичных сигналов для кодирования данной совгкуп 11 651ности сообщений в соответствии с таблицвей будет равноЮ = Х п. и, = 1 О 2 + 9 2 + б 3 ++ 4 3 + 44 + 3 4 + 3 4 + + 1 4 = 112.В рассмотренном же кодеке для размещения неравномерных комбинаций отводится 118 позиций, значит, на оставшихся шести свободных позициях можно разметить еще определенное число комбинамй, например х и хз, тогда 1 =1 и комбинация 1 будет иметь значение 01. При использовании же равномерных комбинаций в кодовом блоке можно закодировать только 40 элементарных сообщений, так как каждое из них содержит три двоичных посылки, а для размещения отводится 120 позиций. Таким образом, при одинаковой достоверности (исправляется однократная ошибка)в рассмотренном кодеке передается на две комбинации больше. Формула изобретенияПомехоустойчивый кодек для передачи дискретных сообщений, включающий кодер и декодер, кодер содержит первый блок постоянной памяти, первый регистр сдвига, второй регистр сдвига, параллельные выходы которого соединены с информационными входами Формирователя проверочных символов, декодер содержит блок коррекции ошибок, первый и второй регистры сдвига и первый блок постоянной памяти, о т - л и ч а ю щ и й с я тем, что, с целью повышения информативности, в кодер введены делитель частоты, первый и второй счетчики импульсов, компаратор, Формирователь импульсов, триггер, источник постоянного кода элемент И и второй блок постоянной памяти, адресные входы которого объединены с соответствующими адресными входами первого блока постоянной памяти и являются информационными входами кодера, вход делителя частоты объединен с первым входом элемента И и является тактовым входом кодера, выход делителя частоты подключен к входам разрешения выборки блоков постоянной памяти, входам разрешения записи первых регистрасдвига и счетчика импульсов и первому установочному входу триггера, выход которого и выход элемента И соединеныинформационным входом декодера, выходы блока коррекции ошибок соединены с установочными входаж первого регистра сдвига, тактовый вход которого объединен с тактовым входом второго регистра сдвига, первым входом третьего элемента И, счетным входом второго счетчика импульсов и первым установочным входом второго триггера и является тактовым входом декодера, параллельные выходы первого регистра сдвига подключены к установочным входам первого счетчика импульсов, выход которого соединен с первым установочным входом первого триггера, выход которого подключен к первым входам первого и второго элементов И и вто-, рому входу третьего элемента И, выход которого соединен со счетнымвходом первого счетчика импульсов,40 45 50 55 385 12соответственно с входом запуска итактовым входом формирователя импульсовы, выход которого подключен к счетным входам счетчиков импульсов и тактовым входам регистров сдвига, выходы первого блока постоянной памятисоединены с установочными входами первого регистра сдвига, выход которогоподключен к информационному входувторого регистра сдвига, выходы второго блока постоянной памяти соединены с установочными входами первогосчетчика мпупьсов и первым входомкомпаратора, выход которого подключен к второму входу элемента И, входам разрешения записи вторых счетчиков импульсов и регистра сдвига иуправляющему входу формирователя про= 20 верочных символов, выходы которогосоединены с первыми установочнымивходами второго регистра сдвига, выход пеового счетчика импульсов подключен к второму установочному вхо ду триггера, выходы источника постоянного кода подключены к установочнымвходам второго счетчика импульсов,выходы которого соединены с вторымивходами компаратора и вторыми уста новочными входами второго регистрасдвига, последовательный выход которого является выходом кодера, в де"кодер введены второй блок постоянной памяти, первый - третий счетчикиимпульсов, первый и второй триггеры.первый - третий, элементы И, генератор импульсов, дешифратор, компаратор и элемент ИЛИ, информационныйвход блока коррекции ошибок является10 Р, (х) Неравномерные кодовые комбинации двоичных сигналов Элементарные сообщения источника 15 0,25 0,23 0,15 0,10 0,09 0,08 ,07 0,03 1 1 1 0011010 001 1 001 0 0001 0000 ххх,5ххт25 13 165 выход второго счетчика импульсов подключен к управляющему входу блока коррекции ошибок, второму установоч" ному входу первого триггера и входам разрешения записи первого счетчика импульсов и первого регистра сдвига, последовательный выход которого соединен с вторым входом первого элемента И, выход которого подключен к информационному входу второго регистра сдвига, выходы которого соединены с адресными входами первого блока постоянной памяти и первыми входами компаратора, выходы генератора импульсов и второго триггера подключены к второму и третьему входам второго элемента И, вхоп которого соединен со счетным входом третьего счетчика импульсов, выходы которого подключены к адресным входам второго блока постоянной памяти и входам дешифратора, выход которого соединен с первым входом элемента ИЛИ, выход которого подключен к второму уста 385 14новочному входу второго триггера, выХоды второго блока постоянной памяти соединены с вторыми входами компаратора, выход которого подключен квторому входу элемента ИЛИ и входу разрешения выборки первого блока постоянной памяти, выходы которого являются выходами декодера.1 б 51385 Составитель О.РевинскиРедактор С.Пекарь Техред А.Кравчук," рректор С.Шекмар аказ 1611 Тираж 479 ПодписноеНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ С113035, Москва, Ж, Раушская. наб., д. 4/5 Производственно-издательский комбинат "Патент", г. Ужгород, ул. Гагарина, 1