Устройство для декодирования недвоичных неразделимых кодов Советский патент 1989 года по МПК H03M13/19 

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

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

На чертеже приведена блок-схема устройства.

ст)ойство содержит опознаватель 1 полярности импульсов, элемент НЕ 2 первый и второй последовательно-паралельные преобразователи 3 и 4 кода, первый - TpcTuii блоки 5-7 оперативной памяти, первый - четвертьй . определители 8-11 весов возможных ошибок, блок 12 постоянной памяти, определитель 13 ошибок минимального веса, определитель 14 ошибок максимального веса, кольцевой счетчик 15, параллельно-последовательный преобразователь 16 кода и блок 17 синхронизации.

Определители 8, 9 и 13 работают в метрике Минковского, а определите- ди 10, 11 и 14 - в метрике Хэмминга.

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

Пусть заданы два кодовых слова

х, ..., ХрТ и у у, ,

йес слова X определя- сумма весов СО (х;) его ко

JL.40

ординат СО t (х;),в частности

СО(Х,) |х;1

по Минковскому и

Минковского не меньше, чем в метрике Хзмминга. Пусть теперь заданы не дв-, а некоторая совокупность кодовых слов, тогда очевидно, что минимальное кодовое расстояние для любых двух кодовых слов в метрике Минковско го не меньше, чем в метрике Хэмминга:

W ( V miri

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

п, Ii2Sl M niaLL

may j.-j.

где J - определение целой части

I

величины.

Отсюда очевидно, что в метрике Минковского U больше, чем в метрике Хэммингао

Дальнейшее изложение идет на примере кода 8В8Т, который использует преобразование восьми двоичных символов в восемь троичных. Код приспособлен для формирования сигнала линейного тракта цифровой системы пере- дачи (ДСП). К тому же, в связи с тем, что канальный интервал почти всех современных ДСП разбит на 8 разрядов, использование преобразования 8В8Т позволяет использовать знания о стати - стике цвоичного источника (если они

Изобретение относится к вычислительной технике и технике связи. Его использование в системах передачи цифровых сигналов с линейными трактами, оборудованными регенераторами многоуровневых (например, трехуровневых) сигналов, позволяет повысить помехоустойчивость устройства, которое содержит опознаватель 1 полярности импульсов, элемент НЕ 2, последовательно-параллельные преобразователи 3, 4 кода, блоки 5-7 оперативной памяти, определители 8, 9 весов возможных ошибок, блок 12 постоянной памяти, определитель 13 ошибок минимального веса, кольцевой счетчик 15, параллельно-последовательный преобразователь 16 кода и блок 17 синхронизации. Введение определителей 10, 11 весов возможных ошибок и определителя 14 ошибок максимального веса позволяет реализовать алгоритм декодирования, в котором определители 8, 9 и 13 работают в метрике Минковского, а определители 10, 11 и 14 - в метрике Хэмминга. При этом помехоустойчивость устройства повышается без снижения удельной скорости передачи. 1 ил., 1 табл.

С0(х ,)

О, если X; О I , если X , 7 О

по Хзммингу.

Расстояние между словами х и у определяется следующей формулой г

(, у) Z1 distdx, - У;/).

Итак, пусть заданы два любых кодовых слоиа X и у. Из определения метрик Хэмминга и Минковского очевидно, что d dj, т.е. для любых двух кодовых слов расстояние в метрике

45 имеются).

Лучшая из таблиц троичных восьмиразрядных слов с минимальным расстоянием 3 содержит 261 троичное восьмиразрядное слово о Минимальное расстояние между любыми двумя словами таблицы равно , 3 в метрике Минковского. 2 лучших по структуре слов этой таблицы составили таблицу троичных слов корректирующего кода 8В8Т,

Распределение диспаритетности слов кода представлено в следующей таблице.

Диспаритетность -3 -2

Количество слов в коде 8В8Т

23

Количество слов, имеющих самые длинные префиксы из одинаковых символов, равно

-1 -I - 20 слов +1 +1 - 18 слов 000 - 7 слов ,

Количество слов, имеющих самые длинные суффиксы из одинаковых символов, равно

-1 -1 - 20 слов +1 +1 - 20 слов 000 - 6 слов

В цифровом потоке не может следовать подряд более 4 одинаковых ненуг левых символов.

Вероятность появления точно 6 следующих подряд аулевых сш-шолов (максимальное количество) в цифровом потоке кода равна 6,4-10 . Вероятность появления точно 5 и 4 следуняцих подряд нулевых символов в цифровом потоке кода равна 3,65-10 и 5,2 10 ,

Пусть декодер кода 8В8Т реализует принцип ограниченного отличия при t{, 1. Пусть в случае, если декодер не найдет среди всех троичных слов кода слова, находящегося на расстоянии, не большем, чем в оси принятого слова, он вьщает в приемник двоичной информации слово, состоящее из 8 нулевых символов. Тогда декодер в среднем (на одно слово) обнаруживает 27, 44 ошибки типа 2К1П (на один порядок в 2 символах) и 88,3 ошибки типа 1К2П (на 2 порядка в 1 символе).

Исправления ошибок 2К1П и 1К2П нет а средние коэффициенты их размножения в двоичном восьмиразрядном блоке соответственно равны 3,76 и 3,87,

Пусть декодер кода 8В8Т реализует принцип ограниченного отличия при 4j 1, Пусть в случае, если деко- дер не найдет среди всех троичных слов кода слова, находящегося на расстоянии, не большем, чем 1 от принятого слова, он выдает в приемник двоичной информации слово 00110000 как слово, приводящее к наименьшей средней вероятности ошибки на двоичный символ. Тогда декодер в среднем (также на 1 слово) обнаруживает 27,44

-1 01 23

47

102 47

23

5

0

5

0

Q

0

5

0

5

5

ошибки типа 2К1П и 8,3 ошибки типа 1К2П и исправляет 27/256 ошибок типа 2К1П и 8/256 ошибок 1К2П.

Коэффициенты размножения ошибок типа 2КШ и 1К2П в двоичном восьмиразрядном блоке соответственно равны 2,75 и 3,9.

Пусть декодер кода 8В8Т реализует принцип ограниченного отличия при tp б6 . Пусть в случае, если декодер не найдет среди всех троичных слов кода слова, находящегося на расстоянии, большем, чем 2 от принятого слона, он выдает в приемник двоичной информации слово 00110000 как слово, приводящее к наименьшей средней вероятности ошибки на двоичный символ, а если декодер не найдет среди всех слов кода слов, находящихся на расстоянии, меньшем, чем 2 от принятого, найдет несколько слов кода, находящихся на расстоянии 2 от принятого, то пусть он выдает в приемник двоичной информации то из этих слов, которое было найдено последним. Тогда декодер в среднем (на одно кодовое слово) обнаруживает 27,44 ошибок типа 2КШ и 3,3 ошибки типа 1К2П и направляет 11,13 ошибки типа 2КШ и 6,48 ошибку 1К2П.

Коэффициенты размножения ошибок 2К1П и 1К2П в двоичном восьмиразрядном блоке соответственно равны 3,67 и 2,63.

Построение декодера по схеме ограниченного отличия с 3 при увеличении сложности его реализации не вызывает существенного увеличения помехоустойчивостио

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

Если шум в канале носит гауссов- ский характер, то вероятность того, что было передано слово с большим расстоянием в метрике Хэмминга, больше вероятности того, что было передано слоне с меньшим расстоянием в метрике Хэмминга, Следовательно, выбор кодового слова по максимуму расстояния от принятого слова в метри ке Хэмми} га из слов, находящихся на одинаковом расстоянии в метрике Минков ского от принятого слова, позволяет определить наиболее вероятное кодовое слово и таким образом повысить поме- хоустойчивость при декодировании недвоичных неразделимых кодов.

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

1

О

-1

Для пояснения того, как определяются критерии выбора наиболее вероятного, рассмотрим код с основанием

--1

--2 -2 -2 -2

Допустим, шум в канале носит гаус- совский характер Если декодирование производится в метрике Хэмминга, то вероятность ошибки определяется по известной формуле

ош

dx

ф,

Р(-2--1)

рф - Р(-|); Р(

Р(-2 -1)

Фс-) - р (-|); р(-2

р(-1--2) (|); Р(-1 -О) - (РсЬ - PC-);

Р(о- О Ф(|) -Ф(-|); 1--2) -Ф(ф; Р(11-0) Ф(|)-Ф(5|);

Р(

Р(

рике Минковского и определить вес этих этих же векторов в метрике Хэмминга Зная характеристики канала, можно определить вероятность перехода на один уровень в символе Р , на два уровня в символе Pj и т.д. и, следовательно, рассчитать функции правдоподобия для векторов ошибки с одинаковым весом в метрике Минковского, но с различным весом в метрике Хэмминга. Исходя их этого уже можно определить критер Ии выбора (по минимуму или максимуму в метрике Хэмминга) наиболее вефоятностного слова.

Если основание кода q 3, то возможны следующие варианты ошибок:

О

1

1

О

20

q 5. В этом случае возможны q() 20 возможных вариантов ошибок

-2-

-101-

2

где i - расстояние между ближайшими

уровнями многоуровневого сигнала, соответствующего данному многопозиционному коду. Если декодирование производится в

метрике Минковского, то вероятности

ошибок различного типа соответственно

равны:

-2-0) () - Ф(|);

2) Ф(У.

-2) Ф(|); Р(2--1) ф(Ц) -(Р(Ц);

й 2 2 о

,зл,

,5Д

0) (|) -(й). Р(2-. ,) .() -ф(ЗЛ),

Заметим, что возможных переходов на ближайший уровень может быть 8, тогда если обозначить через Р средб(|) (-|) (|) 4Ф() - )

Различных переходов на два уровня 15 чить через P, среднюю вероятность может быть всего 6 и, если обозна- г ерехода на 2 уровня, то

Фф -(-|) 2Ф(-|) (З)

Допустим, что произошла ошибка весом 2 в метрике Минковского. Очевидно, что здесь ВОЗМОЖ1ГЫ два вари- анта построения вектора ошибки: первый - произошла ошибка на 1 пози в 2 символах, обозначим вероятность этого события через Р , второй - произошла ошибка на 2 позиции в 1 символе, обозначим вероятность этог события через Pjj.

Для канала с гауссовским распределением справедливо

.2. Г - .п-2

PJ я: С,- Р,-(1-Р. )

- г.(г-1)-Р.(1-Р,)

.ь г-г

It

с;.р1(1-р„)

- г-Рг (l-Pj)

Если в приведенные выражения подставить значение Р 4 и Pj , то при всех возгюжно реализуемых г(414) выполняется неравенство Р. S Pjj Следовательно, более вероятно, что передавалось слово, при передаче которого в канале произошел первый вариант ошибок. Отметим, что вес обоих вариантов ошибок в метрике Минковского одинаков, а в метрике Хэмминга вес первого варианта вектора ошибок (равный 2) больше веса второго варианта вектора ошибок.

Отсюда видно, что при одинаковом весе вектора ошибки в метрике Минковского большим весом в метрике Хэминга определяют большую вероят1527716

10

нюю вероятность перехода на ближайший уровень, то

1П

8

20

5 О

5

0

5

0

5

ность передачи соответствующего кодового слова.

Устройство работает следующим образом,

В опознавателе 1 полярности импульсов входящая трехуровневая последовательность импульсов 6,(t) разбивается на две двоичные последовательности yj(t;) и Zj(t;) по правилу: У(С;) 1, если 0,(t;) 1, и равняется О в других случаях; z(t; ) -1, если б, (t;) 1 и равняется О в других случаях. Последовательность Zj(t;) формируется на выходе элемента НЕ 2, Затем двоичные последовательности подаются на последова-( тельно-параллельные преобразователи 3 3 и 4. Под воздействием блочных синхроимпульсов с блока 17 в блоки 5 и 6 записьшаются принятые троичные слова, каждое из которых представлено в виде двоичных слов той же длины. За время, равное длительности тактового интервала блочной синхропоследовательности, в определителях 8 и 9 весов в метрике Минковского производится вычисление весов 256 возможных векторов ошибок (вначале осуществляется сложение по модулю 2 соответствующих разрядов принятого слова, поступающего с блока 12 постоянной памяти по адресу, задаваемому кольцевым счетчиком 15, а затем осуществляется собственно измерение полученного веса вектора возможной ошибки в метрике Минковского).

Если определитель 13 ошибки мини- мально о веса в метрике Минковского

n

определит, что вес данного вектора возможной ошибки меньше предыдущего, то дает команду в блок 7 на запись восьмиразряздного слова, которое соответствует данному вектору ошибки. Поскольку записьшаемый в блок 7 адрес есть не что иное, как возможно переданное кодовое слово, то после 25б тактов счетчика 15 в блоке 7 будет записано наиболее вероятное двоичное слово.

Если определитель 13 ошибки минимального веса в метрике Минковского определит, что вес данного вектора возможной ошибки равен предьщущему, то происходит стробирование определителей 10 и 11 весов возможных ошибок, которые определяют вес данного вектора возможной ошибки в метрике Хэмминга, т.е. происходит сравнение принятого слова с записанным в блок 12, которое заключается в сложении по модулю 2 соответствующих разрядов принятого слова и сравниваемого в данный момент слова.

Если определитель 14 ошибки максимального веса (для гауссовского канала) в метрике Хэмминга определит, что вес данного возможного вектора ошибки больше предыдущего, то дает команду в блок 7 на запись восьмиразрядного адреса слова, которое соответствует данному вектору ошибки. Поскольку записываемый в блоке 7 адрес есть не что иное, как возможно переданное двоичное слово, то после 256 тактов счетчика 15 в блоке 7 будет записано наиболее вероятное двоичиое слово. Далее производится параллельно последовательное преобразование в преобразователе 16.

Таким образом, повышается помехоустойчивость устройства.

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

Устройство для декодирования недво- .ичных неразделимых кодов, содержащее опознаватель полярности импульсов,V вход которого объединен с входом блока синхронизации и является входом устройства, первый и второй выходы опозманателя полярности импульсов непосредственно и через элемент НЕ подключены к информационным входам соответственно первого и второго jпоследовательно-параллельных преобра-j зователей кода, выходы которых соединены с информационными входами

10

15

152771612

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

20 преобразователей кода, первого и второго блоков оперативной памяти, кольцевого счетчика, определителя ошибок минимального веса, третьего блока оперативной памяти и параллельно-по25 следовательного преобразователя кода, первые и вторые выходы блока постоянной памяти соединены с вторыми входами соответственно первого и второго опре- - делителей весов возможных ошибок,

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

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

35

40

50

55

1315277Ib14

которого соединен с вторым вхо - го блока оперативной памя - дом разрешения записи треье- ти.