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

 

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

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

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

РЕСПУБЛИН

А1 (19) (Н) «;) 4 Н 03 М 13/00

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

Н АBTOPCHQMY СВИДЕТЕЛЬСТВУ вЂ”. «l

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

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

ПРИ П4НТ СССР

1 (21) 4316312/24-24 (22) 12.10.87 (46) 07.12 ° 89. Бюл.М 45 (71) Одесский электротехнический институт связи им. А.С,Попова (72) P.P.Èeænóìÿí, Ву Ван Ту (VN) и Д.А.-Сирбиладзе (53) 681.325(088.8) (56) Блох Э,Л., Зяблов В,В. Обобщенные каскадные коды. — М.-: Связь, 1976.

Разработка унифицированного цифрового линейного тракта цифровых систем передачи сельской первичной сети

EACC. (Недвоичные корректирующие коды). Отчет по НИР. Рег.М 0183002081.

1984, с.42, рис.3,5. (54) УСТРОЙСТВО ДЛЯ ДЕКОДИРОВАНИЯ НЕДВОИЧНЫХ НЕРАЗДЕЛИМЫХ КОДОВ (57) Изобретение относится к вычислительной технике и технике связи. Его использование в системах передачи цифровых сигналов с линейными трактами, оборудованными регенераторами мно2

ГОУРОвllевых (11а11Р1111еР,. Tj)rx) Iýo13Hеиых) .ИI 11 11OB 11ОЗ ВОЛЯ Ет 130ВЫС13Т b IIОМВ.I 1 устой"ивость устройства, котор1o содержит onoэнават ль l полярности импульсов, элемент НЕ 2, последо11эте11ьно-параллельные преобразоват ли 3 кода, блоки 5-7 оперативной памяти определители 8, 9 весов возможных ошибок, блок 12 постоянной памяти, опредепитель 13 ошибок миним,3льп >ro вес а KOJIbl(pBoII счетчик 15, пар

Введение опредепителей 10, ll Be<.ов возможных ошибок и определителя 14 ошибок максимального веса позволяет реализовать алгоритм декодирования в котором определители 8, 9 и 13 работают в метрике Минковского, а определители 10, ll и 14 — в метрике

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

1 табл.

1527716

«1зоЬретение относится к вычислительной технике и т= õíèêå связи и может быть использовано в системах передачи цифровых сигналов с линей5 ными трактами, оборудованными регенераторами многоуровневых сигналов.

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

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

У тройство содержит опознаватель

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

15, параллельно-последовательный преобразователь 16 кода и блок 17 синхронизации. 25

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

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

Пусть заданы два кодовых слова х= х,, х„, ..., х„иу= у,, у, ..., у„ ° Вес слова х определяJ ется как сумма весов И (x,} его ко-"

40 ординат Q t = у (х ° ), в частности (х;) = )x;) по Минковскому и

О, если х, = 0 („1 (х;)

1, если х; 0 по Хэммингу.

Расстояние между словами х и у

on р ед ел я е тс я следующей формулой

d(x, у) = dist((x; — у ().

i r.!

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

Минковского не меньше, чем в метрике

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

d . d

Mm,è — » и

Тогда, если заданы корректирующие свойства величиной d ;„, то в одной и той же кодовой решетке и метрике

Минковского разместится большее число кодовых слов, чем в метрике Хэмминга, т.,е. мощность кода, построенного в метрике Минковского, больше или равна мощности кода, построенного в метрике Хэмминга: М«,, . М„. Величина максимального выигрыша в удельной скорости передачи определяется максимальHîй мощностью кода, получаемой при плотнейшей упаковке кодов п, (1од M „1

01 ма» где () — определение целой части в ели чины.

Отсюда очевидно, что в метрике

Минковского р больше, чем в метрике .

Хэмминга.

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

Лучшая из таблиц троичных восьмиразрядных слов с минимальным расстоянием 3 содержит 261 троичное восьмиразрядное слово. Минимальное расстояние между любыми двумя словами таблицы равно

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

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

15277!6

-3 -г

2 3

Диспаритетность

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

23 7

102 47 7 23 волов, равно

50

Количество слов, имеющих самые длинные префиксы из одинаковых сим-1 — I — 20 слов +I +1 — 18 слов

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

-1 -1 — 20 слов +! +1 — 20 слов

000 — 6 слов

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

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

Пусть декодер кода 8В8Т реализует принцип ограниченного отличия при

1 ° Пусть в случае, если декодер не найдет среди всех троичных слов кода слова, находящегося на расстоянии, не большем, чем в оси приня- 35 того слова, он выдает в приемник двоичной информации слово, состоящее иэ

8 нулевых символов. Тогда декодер в среднем (на одно слово) обнаруживает

27, 44 ошибки типа 2К1П (на один поря- 40 док в 2 символах) и 88,3 ошибки типа

IК2П (на 2 порядка в 1 символе).

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

Пусть декодер кода 8В8Т реализует принцип ограниченного отличия при

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

IК2П и исправляет 27/256 ошибок типа

2К!П и 8/256 ошибок !К2П.

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

Пусть декодер кода 8В8Т реализует принцип ограниченного отличия при

= с . Пусть в случае, если декодер не найдет среди всех троичных слов кода слова, находящегося на расстоянии, большем, чем 2 от принятого слова, он выдает в приемник двоичной информации слово 00!10000 как слово, приводящее к наименьшей средней вероятности ошибки на двоичный символ, а если декодер не найдет среди всех слов кода слов, находящихся на расстоянии, меньшем, чем 2 от принятого, найдет несколько слов кода, находящихся на расстоянии 2 от принятого, то пусть он выдает в приемник двоичной информации то из этих слов, которое было найдено последним. Тогда декодер в среднем (на одно кодовое слово) обнаруживает 27,44 ошибок типа 2КIП и

3,3 ошибки типа IК2П и направляет !

1,!3 ошибки типа 2К1П и 6,48 ошибку

IК2П.

Коэффициенты размножения ошибок

2К1Л и !К2П в двоичном восьмиразрядном блоке соответственно равны 3,67 и

2,63.

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

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

Если шум в канале носит гауссов— ский характер, то вероятность того, что было передано слово с большим расстоянием в метрике Хэмминга, боль-. ше вероятности того, что было пере15277) 6

-1 — 0 — 1 1 0-1 01 1 — — — 1 О

-2 -1

-1 — -2

0 -2

) — -2

2-2

-2 0 — 1 — 0

0 -1

1 -1

2 — -1

-21 — 11

0 1

1 — 0

2 -0

-2 2 — 1 2

0 — 2

1 2

2 — 1

dx = f (-) >

Р(-2 — — 1) Р (-) — ))) (-") Р(-2 — О) - Р (— ) — @();

d ЗЬ 34 5Ь

Э г г

Р(-г — )) = (— ) — Ф (— ); Р(-2 2) - Р(— );

54 74 7b

Р(-) — -2) - (-) Р(-) — 0) - Р (-) — Р (— );

Ь 4 ЗЬ

2 2 2 (2) () Р(2) (г)

ЗЬ 56 ЬЬ

Р(0- -2) ! (— ) Р(0 -) ) У (-) — У (— );

3h 4 ЗЬ

Ф

2 2

Р(0 — 1) Ф() — Р(— ) Р(0 — 2) У (— );

Ь 34 34

2 2 2

P() -2) Ф (-"); Р(1 1) Р() ) ) (), 54 34 5Ь

Ь 3d

Р() — 0) Р (2) Р(2) Р() — ) !)э дано слово с меньшим расстоянием в метрике Хэмминга, Следовательно, выбор кодового слова по максимуму расстояния or принятого слова в метри ке Хэмминга из слов, находящихся на одинаковом расстоянии в метрике Минков. ского от принятого слова, позволяет определить наиболее вероятное кодовое слово и таким образом повысить ломе- )ð хоустойчивость при декодировании недвоичных неразделимых кодов.

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

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

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

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

Исходя их этого уже можно определить критерии выбора (по минимуму или максимуму в метрике Хэмминга) наиболее вероятностного слова.

Если основание кода q = 3, то возможны следующие варианты ошибок: с) 5. В этом случае возможны с)(с -1)

=20 возможных вариантов ошибок где Ь вЂ” расстояние между ближайшими уровнями многоуровневого сигнала, соответствующего данному многопозиционному коду.

Если декодирование производится в метрике Минковского, то вероятности ошибок различного типа соответственно равны:! о!

527716

Р(2 — 1 -!) = P (--) — ф (.

5Ь 7

2 2

Р(2 — -2) = ф (--) °

7Ь

P(2 0) = ф(--) - y(); Р(2 1) )(!!) ...)(З!!)

ЗЛ 5!!

2 2

11)

2Ф(-

2

4ф(-) — зф(†) d 3!!

1 2 2

6(1) (-) — )) (— )) а

5 8

2

41ф (-) — Р (— )11 +

5 )

2 )

Р

2 6

2ч)(--) 3d

2Ф(-) + P(— )

d ЗЬ

2 2

35

) r-г г (r 1) P (1 P ) РСР(1Р) 40

50

Заметим, что возможных переходов на ближайший уровень может быть 8, тогда если обозначить через P средРазличных переходов на два уровня может быть всего 6 и, если обознаДопустим, что произошла ошибка весом 2 в метрике Минковского. Очевидно, что здесь возможны два варианта построения вектора ошибки: первый — произошла ошибка на 1 позицию в 2 символах, обозначим вероятность этого события через Р,, второй произошла ошибка на 2 позиции в 1 символе, обозначим вероятность этого события через Р,.

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

Р = С,, Р (I-P, )

Если в приведенные выражения подставить значение Р, и Р, то при всех возможно реализуемых r(< 14) выполняется неравенство Р Р,.

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

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

Хэмминга вес первого варианта вектора ошибок (равный 2) больше веса второго варианта вектора ошибок.

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

5 чнть через Р среднюю вероятность перехода на 2 уровня, то ность передачи соответствующего кодоного слова, Устройство работает следующим образом.

В опоэнавателе 1 полярности импульсов входящая трехуровневая последовательность импульсов 0 >(t;) разбивается на две двоичные последовательности у (t, ) и z (t, ) по правилу: у (t, ) = 1, если д (t;)

1, и равняется О в других случаях;

z„(t; ) =.=!, если 8 (t; ) 1 и равняется О в других случаях. Последовательность кг(С,) q)o H eT Hd выходе элемента HE 2, Затем двоичные последовательности подаются на последовательно-параллельные преобразователи 3

3 и 4. Под воздействием блочных синхроимпульсов с блока 17 в блоки 5 и 6 записываются принятые троичные слова, каждое из которых представлено в виде двоичных слов той же длины. 3а время, равное длительности тактового интервала блочной синхропоследовательности, в определителях 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.

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

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

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

7716

45

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

13

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

Составитель О.Ревииский

Техред Л.Олийнык Корректор М.Шароши

Редактор О,Юрковецкая

Тираж 884

3axas 7518/57

Подписное

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

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

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