Устройство для декодирования недвоичных неразделимых кодов

СОЮЗ СОВЕТСНИХСОЦИАЛИСТИЧЕСКИХРЕСПУБЛИН А 1 3 М 13/О ОПИСАНИЕ ИЗОБРЕТЕИИН АВТОРСИОМУ СВИДЕТЕЛЬСТВУ 6 ЮЮ ЮМ%М 4 Ю Ъ ЪЪЮЛ Ч М неиых)Ма ХО -а) а.ЛИ Э,памяти гз ации(54) УСТРОЙСТВО ДВОИЧНЫХ НЕРАЗДЕ (57) Изобретение тельной технике использование вцифровых сигнало ми, оборудованнь ДЛЯ ДЕКОДИРОВАН ЛИМЫХ КОДОВ относится к в д С: слиЕго оичивостьижения и технике свя системах переда в с линейными т та( регенераторами мноОСУДАРСТВЕН 14 ЫЙ НОМИТЕТПО ИЗОБРЕТЕНИЯМ И ОТНРЫТИЯМПРИ П 4 НТ СССР(71) Одес.ский электротехнический институт связи им. А.С,11 опова(72) Р.Р.Межпумян, Ву Ван Ту ("чБ) и Д.А.-Сирбиладзе(56) Блох Э,Л Зяблов В.В, Обобщенны каскадные коды. - М.: Связь, 1976.Разработка унифицированного цифрового линейного тракта цифровых систем передачи сельской первичной сети ЕАСС. (Недвоичные корректирующие коды). Отчет по НИР, Рег,1)а 0183002081 1984, с.42, рис.3,5. ГОУРОВ 11 ЕВЫХ (1)ар)(11 Ер Т)РХурав .И)1,.;1 ОВ, 1(ОЗВОЛЯЕТ доньСИТЬ ПО устой;ивость устройства, которос со- ДСР)аит ОПОЭНанатаЛЬ 1 ПОЛЯРНОСти импульсов, элемент НЕ 2, последо)азте)ьно-параллельные преобразовкода, блоки 5-7 оперативной определители 8, 9 весов возможнь)х Ошибок, блок 12 постоянной памяти, опредепитель 13 Ошибок мини)ь)ль)а го Веса, кольцевой счетчик 15, парЯ 11- лельно-последовательный прсобразова тель 16 кода и блок 17 синхрон) Введение опредепителей 10, 1 весов возможных ошибок и определителя 14 ошибок максимального веса позволяет реализовать алгоритм декодирования в котором определители 8, 9 и 13 работают в метрике Минковского, а о ределители 10, 11 и 14 - в метрике Хэмминга, При этом помехоуст устройства повьшается без сн удельной скорости передачи.ил 1 табл.1527716 с 1, - с 1 М ,Х а 1 о по Минковскому и О, если х, = 0 1, если х, 0 ЙзоЬретение относится к вычислительной технике и технике связи и может быть использовано в системахпередачи цифровых сигналов с линей 5ными трактами, оборудованными регенераторами многоуровневых сигналов.Цель изобретения - повышение помехоустойчивости устройства.На чертеже приведена блок-схема 10устройства,утройство содержит опознаватель1 полярности импульсов, элемент НЕ 2,первый и второй последовательно-парал-,лельные преобразователи 3 и 4 кода, 15первый - третий блоки 5 - 7 оперативной памяти, первый - четвертый .определители 8 - 11 весов возможныхошибок, блок 12 постоянной памяти,определитель 13 ошибок минимальноговеса, определитель 14 ошибок максимального веса, кольцевой счетчик15, параллельно-последовательный преобразователь 16 кода и блок 17 синхронизации. 25Определители 8, 9 и 13 работаютв метрике Минковского, а определитеди 10, 11 и 14 - в метрике Хэмминга.Использование различных метрикпозволяет совместить возможность выигрыша удельной скорости передачиинформации с коррекцией ошибок. Этоутверждение можно обосновать следующим образом,Пусть заданы два кодовых словах ххх и у у( уУ, , у . Вес слова х определяется как сумма весов И (х,) его ко-"40ординат Сд с; =с,1(х ), в частностии(х;) = х;1 по Хэммингу.Расстояние между словами х и у50оп р ед ел я е тс я сл е дующей формулой с 1(х, у) = с 1 дз(х; - у,.с. Итак, пусть заданы два любых кодовых слова х и у, Из определения мет 55 рик Хэмминга и Минковского очевидно, что с 1,с 1, т.е. для любых двух кодовых слов расстояние в метрике Минковского не меньше, чем в метрикеХэммикга. Пусть теперь заданы не два некс торая совокупность кодовыхслов, тогда очевидно, что минимальное ксдовое расстояние для любыхдвух кодовых слов в метрике Минковско-,го не меньше, чем в метрике Хэмминга: Тогда, если заданы корректирующие свойства величиной с 1 ;, то в одной и той же кодовой решетке и метрике Минковского разместится большее число кодовых слов, чем в метрике Хэмминга, т.,е. мощность кода, построенного в метрике Минковского, больше или равна моиности кода, построенного в метрике Хэмминга; М, М. Величина максимального выигрыша в удельной скорости передачи определяется максимальной мощностью кода, получаемой при плотнейшей упаковке кодови а, 1 оаМЩма г г где 1 1 - определение целой части величины. 1Отсюда очевидно, что в метрике Минковского р больше, чем в метрике Хэмминга.Дальнейшее изложение идет на примере кода 8 В 8 Т, который использует преобразование восьми двоичных символов в восемь троичных, Код приспособлен для формирования сигнала линейного тракта цифровой системы пере- дачи (ЦСП). К тому же, в связи с тем, что канальный интервал почти всех современных ЦСП разбит на 8 разрядов, использование преобразования 8 В 8 Т позволяет использовать знания о стати 1 стике цвоичного источника (если они имеются). Лучшая из таблиц троичных восьмиразрядных слов с минимальным расстоянием 3 содержит 261 троичное восьмиразрядное слово. Минимальное расстояние между любыми двумя словами таблицы равно 3 в метрике Минковского. 2 з лучших по структуре слов этой таблицы составили таблицу троичных спов корректирующего кода 8 В 8 Т. Распределение диспаритетности словкода представлено в следующей таблице.-3 -г 2 3 Диспаритетность Количество словв коде 8 В 8 Т 23 7 47 102 47 7 23 волов, равно 10 50 55 Количество слов, имеющих самые длинные префиксы из одинаковых сим-1 - 1 - 20 слов +1 +1 - 18 слов 000 - 7 слов,Количество слов, имеющих самые длинные суффиксы иэ одинаковых символов, равно-1 -1 - 20 слов + +1 - 20 слов000 - 6 слов20 В цифровом потоке не может следовать подряд более 4 одинаковых нену-. левых символов.Вероятность появления точно 6 следующих подряд нулевых символов (мак 25 симальное количество) в цифровом пото ке кода равна 6,4 10 . Вероятность появления точно 5 и 4 следующих подряд нулевых символов в цифровом потоке кода равна 3,65 10 и 5,2 10Пусть декодер кода 8 В 8 Т реализует принцип ограниченного отличия при1Пусть в случае, если декодер не найдет среди всех троичных слов кода слова, находящегося на расстоянии, не большем, чем в оси приня того слова, он выдает в приемник двоичной информации слово, состоящее иэ 8 нулевых символов. Тогда декодер в среднем (на одно слово) обнаруживает 27, 44 ошибки типа 2 К 1 П (на один порядок в 2 символах) и 88,3 ошибки типа 1 К 2 П (на 2 порядка в 1 символе).Исправления ошибок 2 К 1 П и 1 К 2 П нет, а средние коэффициенты их размножения в двоичном восьмиразрядном блоке соот ветственно равны 3,76 и 3,87. Пусть декодер кода 8 В 8 Т реализует принцип ограниченного отличия при С,1, Пусть в случае, если декодер не найдет среди всех троичных слов кода слова, находящегося на расстоянии, не большем, чем 1 от принятого слова, он выдает в приемник двоичной информации слово 00110000 как слово, приводящее к наименьшей средней вероятности ошибки на двоичный символ. Тогда декодер в среднем (также на 1 слово) обнаруживает 27,44 ошибки типа 2 К 1 П и 8,3 ошибки типа 1 К 2 П и исправляет 27/256 ошибок типа 2 К 1 П и 8/256 ошибок К 2 П.Коэффициенты размножения ошибок типа 2 К 1 П и 1 К 2 П в двоичном восьмиразрядном блоке соответственно равны 2,75 и 3,9Пусть декодер кода 8 В 8 Т реализует принцип ограниченного отличия при= М, . Пусть в случае, если декодер не найдет среди всех троичных слов кода слова, находящегося на расстоянии, большем, чем 2 от принятого слова, он выдает в приемник двоичной информации слово 0010000 как слово, приводящее к наименьшей средней вероятности ошибки на двоичный символ, а если декодер не найдет среди всех слов кода слов, находящихся на расстоянии, меньшем чем 2 от принятого, найдет несколько слов кода, находящихся на расстоянии 2 от принятого, то пусть он выдает в приемник двоичной информации то из этих слов, которое было найдено последним. Тогда декодер в среднем (на одно кодовое слово) обнаруживает 27,44 ошибок типа 2 К 1 П и 3,3 ошибки типа 1 К 2 П и направляет 11,13 ошибки типа 2 К 1 П и 6,48 ошибку 1 К 2 П.КоэфФициенты размножения ошибок 2 К 1 Л и 1 К 2 П в двоичном восьмиразрядном блоке соответственно равны 3,67 и 2,63.Построение декодера по схеме ограниченного отличия съ 3 при увеличении сложности его реализации не вызывает существенного увеличения помехоустойчивости.Особенность работы устройства заключается в следующем. Принятое кодовое слово сравнивается со всеми кодовыми словами по минимуму расстояния в метрике Минковского и выбирается ближайшее словоЕсли же таких слов несколько, то все они сравниваются с принятым в метрике Хэмминга. Если шум в канале носит гауссов -ский характер, то вероятность того,что было передано слово с большимрасстоянием в метрике Хэмминга, боль-.ше версятности того, что было пере1527716 дано слово с меньшим расстоянием в метрике Хэмминга, Следовательно, выбор кодового слова по максимуму расстояния от принятого слова в метри ке Хэмминга из слов, находящихся на одинаковом расстоянии в метрике Минков ского от принятого слова, позволяет определить наиболее вероятное кодовое слово и таким образом повысить помехоустойчивость при декодировании недвоичных неразделимых кодов.Если характер шума в канале отличается от гауссовского, то необходимо определить возможные векторы ошиб ки в метрике Минковского, найти векторы ошибки с минимальным весом в мет- 0 - 1 -1 О- -1 0 - 1 1 -- в1 - 0 20Для пояснения того как определяются критерии выбора наиболее вероятного, рассмотрим код с основанием-2 - 2 - 1 - 2 О - 2 1 - 2 2 - 1 30 где Ь - расстояние между ближайшимиуровнями многоуровневого сигнала, соответствующего данномумногопозиционному коду.Если декодирование производится в 35 метрике Минковского, то вероятностиошибок различного типа соответственноравны: йх = У (-)1ЬР(О 1) - Ч(-) - У( - ) Р(О 2) - У ( - );Ь ЗЬ ЗЬ 2 2 2 Р( г) - Ф( ), Р(1- 1) У( ) ( 2), 5 Ь ЗЬ 5 Ь Ь 36Р( О) -У( ) Ф( ),Допустим, шум в канале носит гауссовский характер. Если декодирование производится в метрике Хэмминга, то вероятность ошибки определяется по известной формуле рике Минковского и определить вес этихэтих же векторов в метрике ХэммингаЗная характеристики канала, можноопределить вероятность перехода наодин уровень в символе Р 1., на два уровня в символе Р и т.д. и, следовательно, рассчитать функции правдоподобиядля векторов ошибки с одинаковымвесом в метрике Минковского, но сразличным весом в метрике Хэмминга,Исходя их этого уже можно определитькритерии выбора (по минимуму илимаксимуму в метрике Хэмминга) наиболее вероятностного слова,Если основание кода и = 3, товозможны следующие варианты ошибок: с = 5. В этом случае возможны с 1(с))-фг Р) (1-Р ) 45 50 55 Заметим, что возможных переходовна ближайший уровень может быть 8,тогда если обозначить через Р, средРазличных переходов на два уровняможет быть всего 6 и, если обознаДопустим, что произошла ошибка весом 2 в метрике Минковского. Очевидно, что здесь возможны два варианта построения вектора ошибки: первый - произошла ошибка на 1 позицию в 2 символах, обозначим вероятность этого события через Р, второй произошла ошибка на 2 позиции в 1 символе, обозначим вероятность этого события через РДля канала с гауссовским распределением справедливоО. гР= СР(1 Р)1 Если в приведенные выражения подставить значение Р, и Р, то при всех возможно реализуемых г(14) выполняется неравенство РР,. Следовательно, более вероятно, что передавалось слово, при передаче которого в канале произошел первый вариант ошибок. Отметим, что вес обоих вариантов ошибок в метрике Минковского одинаков, а в метрике Хэмминга вес первого варианта вектора ошибок (равный 2) больше веса второго варианта вектора ошибок.Отсюда видно, что при одинаковом весе вектора ошибки в метрике Минковского большим весом в метрике Хэм минга определяют большую вероятнюю вероятность перехода на ближайший уровень, то 5 чнть через Рг среднюю вероятность пе 1 ехода на 2 уровня, то ность передачи соответствующего кодоного слова,Устройство работает следующимобразом.В опоэнавателе 1 полярности импульсов входящая трехуровневаяпоследовательность импульсов 9 (г;)разбивается на две двоичные последовательности у(Г ) и г(Г,) поправилу: у (г;) = 1, если д (г;)1, и равняется 0 в других случаях;г(Г; ) ==, если 91 (Г; ) 1 и равняетВся 0 в других случаях. Последовательность г(Г;) формируется на выходеэлемента НЕ 2, Затем двоичные последовательности подаются на последова-тельно-параллельные преобразователи 33 и 4. Под воздействием блочных синхроимпульсов с блока 17 в блоки 5 и 6записываются принятые троичные слова,каждое из которых представлено в видедвоичных слов той же длины. За время,равное длительности тактового интервалаблочной синхропоследовательности, вопределителях 8 и 9 весов в метрикеМинковского производится вычислениевесов 256 возможных векторов ошибок(вначале осуществляется сложение помодулю 2 соответствующих разрядов принятого слова, поступающего с блока 12постоянной памяти по адресу, задаваемому кольцевым счетчиком 15, а затемосуществляется собственно измерениеполученного веса вектора возможнойошибки в метрике Минковского).Если определитель 13 ошибки минимально, о веса в метрике Минковского11 152определит, что вес данного векторавозможной ошибки меньше гредыдущего,то дает команду в блок 7 на записьвосьмиразряздного слова, котороесоответствует данному вектору ошибки.Поскольку записываемый в блок 7 адрессеть не что иное, как возможно переданное кодовое слово, то после 256тактов счетчика 15 в блоке 7 будетзаписано наиболее вероятное двоичноеслово.Если определитель 13 ошибки минимального веса в метрике Минковскогоопределит, что вес данного векторавозможной ошибки равен предыдущему,то происходит стробироваиие определителей 10 и 11 весов возможных ошибок,которые определяют вес данного векторавозможной ошибки в метрике Хзммиига,т.е. происходит сравнение принятогослова с записанным в блок 12, котороезаключается в сложении по модулю 2соответствующих разрядов принятогослова и сравниваемого в данный моментслова,Если определитель 14 ошибки максимального веса (для гауссовского канала) в метрике Хэмминга определит,что вес данного возможного вектораошибки больше предыдущего, то даеткоманду в блок 7 на запись восьмираэрядного адреса слова, которое соответствует данному вектору ошибки. Поскольку записываежй в блоке 7 адресесть не что иное, как возможно переданное двоичное слово, то после 256тактов счетчика 15 в блоке 7 будетзаписано наиболее вероятное двоичноеслово. Далее производится параллельнопоследовательное преобразование впреобразователе 16.Таким образом, повышается помехоустойчивость устройства. формула изобретенияУстройство для декодирования недво,ичных неразделимых кодов, содержащее опознаватель полярности импульсов,1 вход которого объединен с входом блока синхронизации и является входом устройства, первый и второй выходы опоэнгвателя полярности импульсов непосредственно и через элемент НЕ подключены к информационным входам соответственно первого и второго последовательно-параллельных преобра- эователей кода, выходы которыхсоединены с информационными входами12 7716 40 45 50 55 10 15 20 25 30 35 одноименных блоков оперативной памяти, выходы которых подключены к первым входам одноименных определителей весов возможных ошибок, выходы которых соединены соответственно с первы. ми и вторыми информационными входами определителя ошибки минимального веса, кольцевой счетчик, выходы которого подключены к входам блока постояннойпамяти и информационным входам третьего блока оперативной памяти, выходыкоторого соединены с информационнымивходами параллельно-последовательногопреобразователя кода, выход которогоявляется выходом устройства, первыйшестой выходы блока синхронизации подключены к тактовым входам соответственно последовательно-параллельныхпреобразователей кода, первого и второго блоков оперативной памяти, кольцевого счетчика, определителя ошибокминимального веса, третьего блокаоперативной памяти и параллельно-последовательного преобразователя кода,первые и вторые выходы блока постоянной памяти соединены с вторыми входамисоответственно первого и второго определителей весов возможных ошибок,о т л и ч а ю щ е е с я тем, что, сцелью повышения помехоустойчивостиустройства, в него введены третий ичетвертый определители весов возможных ошибок и определитель ошибокмаксимального веса, тактовый входкоторого подключен к четвертому выхоцу блока синхронизации, первые и вторые информационные входы третьего определителя весов возможных ошибокподключены соответственно к выходам первого блока оперативной памяти ипервым выходам блока постоянной памя"ти, первые и вторые информационныевходы четвертого определителя весоввозможных ошибок подключены соответственно к выходам второго блока опера 1 тивной памяти и вторым выходам блокапостоянной памяти, первый выход определителя ошибок минимального веса подключен к первому входу разрешения записи третьего блока оперативной памяти, второй выход определителя-ошибок минимального веса соединен со стробирующими входами третьего ичетвертого определителей весов возможных ошибок, выходы которых подклю, чены соответственно к первым и вторым информационным входам определителя ошибок максимального веса, выход О14 13 1527 71 ь которого соединен с вторым вхо - го блока оперативной намядом разрешения записи треье- ти. Составитель О.РевиискийТехред Л.Олийнык Корректор М,Шароши Редактор О.Юрковецкая Тираж 884 Заказ 7518/57 Подписное ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР 113035, Москва, Ж, Раушская наб., д. 4/5