Способ декодирования нелинейного кода и устройство для его осуществления

 

1. Способ декодирования нелинейного кода

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

3 Ф

РЕСПУБЛИН ае 01) эы Н 04 L 1 10; Н 03 К 13/32

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

ГЮ ДЕЛАМ ИЗОБРЕТЕНИЙ И (ЛНРЫТИЙ

ОПИСАНИЕ ИЗОБРЕТЕНИЯ 1" В н aevoaceow свидвтаъетвьг (.21) 3215375/18-09 (22) 05 ° 12 ° 80 . (46) 15.08.84, Бюл. 11 30 (72) Ю.П. Пятошин, В.А. Тузиков и А.И. Шутиков (53) 621 ° 394 . 14 (56) 1. Патент ФРГ В 1931941, кл. Н 03 К 13/22, 1978.

2. Р.Ж.Как. Вильямс и др. Теория кодов, исправляющих ошибки. М., "Связь", 1979, с. 18-20 (прототип). (54) СПОСОБ ДЕКОДИРОВАНИЯ НЕЛИНЕЙНОГО КОДА И УСТРОЙСТВО ДЛЯ ЕГО ОСУЩЕСТВЛЕН ИЯ. (57) 1. Способ декодирования нелинейного кода (16,8), представляемого в виде каскадного кода, состоящего иэ четверичного кода Рида-Соломона и двоичного кода, основанный на поразрядном сравнении принятого слова с кодовыми словами и определении ближайшего от принятого слова по расстоянию Хэмминга о т л и ч а ю.шийся тем, что, с целью упрощения декодирования, принятое слово разбивают на четыре группы по четыре символа в каждой, преобразуют в кодовые слова кода Рида-Соломона в соответствии с его порождающей матрицей, сравнивают каждую группу из четырех символов с каждой из групп из четырех символов первого и второго подмножества двоичного кода, при совпадении каждой из трех или четырех групп из четырех символов каждая с одной из групп символов только первого нли только второго подмножества двоичного кода декодирование осуществляют в два этапа, причем на первом этапе сравнивают преобразованное иэ принятого слова кода (16,8) кодовое слово Рида-Соломона с последовательно перебираемыми кодовыми словами кода Рида-Соломона, сформированными из первых четырех информационных символов кода (16,8), причем при расстоянии

Хэмминга между сравниваемыми словами нуль или единица запоминают пер-. вые четыре информационных символа . кода(16,8),а на втором этапе поразрядно сравнивают принятое слово с последовательно перебираемыми словами кода (16,8) при неизменных первых четырех информационных символах кода (16,8),причем при расстоянии g

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

Ф групп символов только первого или только второго подмножества двоичного кода осуществляют операции первого и второго этапов, причем на

1 первом этапе первые четыре информационных символа кода (16,8) запоминают при совпадении двух иэ четырех символов, взятых из первого подмножества в сравниваемых словах, и заканчивают декодирование, а в случае несоответствия на втором этапе сравнения по расстоянию Хэмминга нуль, один или два повторяют операции для первого и второго этапов, причем на первом этапе четыре информационных символа кода (16,8) запоминают при совпадении двух иэ четырех символов, взятых из второго подмножества в сравниваемых словах, и заканчивают декодирование.

11

2. Устройство для декодирования нелинейного кода (16,8), содержащее тактовый генератор и последовательно соединенные кодер кода (16,8),блок поразрядного сравнения и первый пороговый элемент, причем вторая группа входов блока поразрядного сравнения является выходами устройства, о т л и ч а ю щ е е с я тем, что с целью сокращения времени декодирования, введены последовательно соединенные преобразователь принятого слова, блок сравнения и второй пороговый элемент, а также два блока управления, два блока элементов И, два элемента ИЛИ-НЕ, три элемента И, элемент ИЛИ, четырехразрядный счетчик, нятираэрядный счетчик, кодер

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

08618 входу которого подключен выход второго порогового элемента, при этом выходы первого и второго блоков элементов И подключены соответственно к входам первого и второго элементов ИЛИ-НЕ, выходы которых подключены соответственно к вторым входам второго и третьего элементов И, при этом выходы четырехразрядного счетчика являются выходами устройства и подключены к первой группе входов кодера кода (16,8) и входам кодера Рида-Соломона, выходы которого подключены к второй группе выходов блока сравнения, выходы пятиразрядного счетчика являются выходами устройства и подключены к второй группе входов кодера кода (16,8), выход тактового генератора подключен к первым входам первого и второго блоков управления, причем первый выход первого блока управления подключен к первому входу четырехразрядного счетчика, а выход второго блока управления подключен к первому входу пятиразрядного счетчика, пятый разряд которого подключен к вторым входам первого и второго блоков управления, выход элемента ИЛИ подключен к третьему входу первого блока управления, а к третьему входу второго блока управления подключен выход первого порогового элемента, а четвертые входы первого и второго блоков управления и вторые входы пятиразрядного и четырехразрядного счетчиков являются входом стартового сигнала, а второй выход первого блока управления подключен к пятому входу второго блока управления.

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

Известен способ декодирования корректирующих кодов, заключающийся в том, что принятые слова сравниваются с возможными кодовыми словами, по результатам сравнения выбирается слово с наилучшей корреляцией(1), 2

Однако .известный способ предназначен для декодирования широкого класса кодов и поэтому для конкретного кода (16,8) требует большое количество операций.

Известно устройство, реализующее споСоб декодирования корректирующих кодов, содержащее корреляционный детектор, первичный детектор, а также синхронизатор и логический блок, к входам которого под618

Э 1108 ключены выходы детекторов и синхронизатора t1 ).

Однако известное устройство имеет большое время декодирования.

Наиболее близким к изобретению 5 является способ декодирования нелинейного кода (16,8), представляемого в виде каскадного кода, состоящего из четверичного кода Рида-Соломона и двоичного кода, основанный на !О

Ф поразрядном сравнении принятого слова с кодовыми словами и определении ближайшего от принятого слова по расстоянию Хэмминга, причем принятое слово сравнивают со всеми возможными 15 словами (2 3.

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

Известно устройство, реализующее способ декодирования нелинейного кода

1 содержащее тактовый генератор и пос— ледовательно соединенные кодер кода (16,8), блок поразрядного сравнения 25 и первый пороговый элемент, причем вторая группа входов блока поразрядного сравнения является входом устройства (2 ).

Однако известное устройство обла- 311 дает большим временем декодирования.

Цель изобретения - упрощение декодирования и сокращение времени декодирования.

Указанная цель достигается тем

35 что согласно способу декодирования нелинейного кода (16,8), представляемого в виде каскадного кода, состоящего из четверичного кода Рида-Соломона и двоичного кода основанному

У 40 на поразрядном сравнении принятого слова с кодовыми словами и определении ближайшего от принятого слова по расстоянию Хэмминга, принятое слово разбивают на четыре группы по 45 четыре символа в каждой, преобразуют в кодовые слова кода Рида-Соломона в соответствии с его порождающей матрицей, сравнивают каждую группу, из четырех символов с каядой из 50 групп из четырех символов первого и второго подмножества двоичного кода, при совпадении каядой из трех или четырех групп из четырех символов каядая с одной из групп символов только первого или только второго под55 множества двоичного кода декодирование осуществляют в два этапа причем на первом этапе сравнивают преобразование из принятого слова кода (16,8) кодовое слово Рида-Соломона с последовательно перебираемыми кодовыми словами кода Рида-Соломона, сформированными из первых четырех информационных символов кода (16,8), причем при расстоянии Хэмминга между сравниваемыми словами нуль или единица запоминают первые четыре информационных символа кода (16,8), а на втором этапе поразрядно сравни" вают принятое слово с последовательно перебираемыми словами кода (16,8) при неизменных первых четы» рех информационных символах кода (16,8), причем при расстоянии Хэмминга между сравниваемыми словами нуль, один или два запоминают вторые четыре информационных символа и заканчивают декодирование, а при совпадении каядой из двух групп из четырех символов каядая с одной из групп символов только первого или только второго подмножества двоичного кода осуществляют операции первого и второго этапов, причем на первом этапе первые четыре информационных символа кода (16,8) запоминают при совпадении двух из четырех символов, взятых из первого подмножества в сравниваемых словах, и заканчивают декодирование, а в случае несоответствия на втором этапе сравнения по расстоянию Хэмминга нуль, один или два повторяют операции для первого и второго этапов, причем на первом этапе четыре информационных символа кода (16,8) запоминают при совпадении двух иэ четырех символов, взятых из второго подмножества в сравниваемых словах, и заканчивают декодирование.

При этом в устройство для декодирования нелинейного кода (16,8), содержащее тактовый генератор и последовательно соединенные кодер кода (16,8), блок поразрядного сравнения и первый пороговый элемент, причем вторая группа входов блока поразрядного сравнения является выходами устройства, введены последовательно соединенные преобразователь принятого слова, блок сравнения и второй пороговый элемент, а также два блока управления, два блока элементов И, два элемента ИЛИ-НЕ, три элемента И, элемент ИЛИ, четырехразрядный счетчик, кодер Рида-Соломона, обнаружитель

5 11086 ошибок и дешифратор, входы которого объединены с входами преобразователя принятого слова и второй группой входов блока поразрядного сравнения, при этом выходы блока сравнения нодключень> к первым входам первого и второго блоков элементов И, причем инверсные входы де»>ифратора подключены к вторым входам первого блока элементов И, а прямые >о выходы дешифратора подключены к вторым входам второго блока элементов И и к входам обнаружителя ошибок, прямой выход которого подключен к первому входу первого элемента И, а инверсный выход обнаружителя ошибок подключен к первым входам второго и третьего элементов И, выходы которых подключены к первому и второму входам элемента ИЛИ, к третьему входу которого подключен выход первого элемента И, к второму входу которого подключен выход второго порогового элемента, при этом выходы первого и второго блоков элементов И подключены соответственно к входам первого и второго элементов ИЛИ-НЕ, выходы которых подключены соответственно к вторым входам второго и третьего элементов И, при этом выходы четырехразрядного счетчика являются выходами устройства и подключены к первой группе входов кодера кода (16,8) и входам кодера

Рида-Соломона, выходы которого под„35 ключены к второй группе входов блока сравнения, выходы пятиразрядного счетчика являются выходами устройства и подключены к второй группе входов кодера кода (16,8), выход тактового

40 генератора подключен к первым входам первого и второго блоков управления, причем первый выход первого блока управления подключен к первому входу четырехразрядного счетчика, а

45 выход второго блока управления подключен к первому входу пятиразрядного счетчика, пятый разряд которого подключен к вторым входам первого и второго блоков управления, 50 выход элемента ИЛИ подключен к третьему входу первого блока управления, а к третьему входу второго

18 Ь блока управления подключен выход первого порогового элемента, а четвертые входы первого и второго блоков управления и вторые входы пятиразрядного и четырехразрядного счетчиков являются входом стартового сигнала, а второй выход первого блока управления подключен к пятому входу второго блока управления.

На фиг.1 представлена структурная электрическая схема устройства декодирования нелинейного кода, на фиг.2 — то же, кодера кода Рида-Соломона; на фиг.3 — - то же, блока сравнения.

Устройство для декодирования нелинейного кода содержит преобразователь 1 принятого слова, дешифратор 2, обнаружитель 3 ошибок, пятиразрядный счетчик 4, кодер 5 кода (16,8), четырехразрядный счетчик 6, кодер 7 кода Рида-Соломона, блок 8 сравнения, первый блок 9 управления,тактовый генератор 10, второй блок 11 управления, первый пороговый элемент 12, блок 13 поразрядного сравнения, первый 14 и второй 15 блоки элементов И, второй пороговый элемент 16, первый 17 и второй 18 элементы ИЛИ-HE первый 19, второй 20 и третий 21 элементы И, элемент ИЛИ 22. Кодер 7 кода Рида-Соломона содержит сумматоры 23-1-23-6 по модулю два, блок 8 сравнения содержит сумматоры 24-1-24-8 по модулю два элементы ИЛИ 25-1-25-4.

Предложенный способ основан на каскадном представлении кода (16,8) в виде четверичного (4,2) кода Рида-Соломона с расстоянием

d„ = 3 и двоичного кода с расстоянием d = 2.

Порождающая матрица G кода

Рида-Соломона имеет вид

0132

Матрица А кода Рида-Соломона, состоящая из кодовых слов а (а,а а а,), à., e 10,1,2,3}, записывается в виде

1108618 оооо

1111

2222

3333

0123

1032

2301

3210

0231

2013

3102

О312

1203

3021 меняется на (0001) и кодовый вектор

25 запишется в виде (1110 0001 0001

0001) .

Устройство для декодирования нелинейного кода работает следующим образом.

gp Сумматоры 23-1-23-6 по модулю два в блоке 8 сравнения соединены в соответствии с табл.1 состоит из всевознаборов Ь

e f 0,13 длины 4, подмножества В, и

Двоичный код можных двоичных

1 2 3 4 разбитых на два в номера номера

Bt ) а, 0

2

1111

0101

0011

1001

0001

0111

1011

1101

1110

Та бли ца 1

В

В

Входы

Выходы

00000000

0000

0001

0010

0011

0100

0101

0110

0111

1000

10000111

10011100

1001

Код (16,8) строится следующим об- 40 разом. Пусть имеются информационные символы (bÄ,Ь,Ъз,b4,Ь,Ьь,b,Ъ ), Ъ; е (0,1) В соответствии с матрицей С производится кодирование части информационных символов (Ь,Ъ Ь,Ь ) 45 в кодовый вектор а кода Рида-Соломона, а = (а„,а,а,à ), a;e)0,1,2 ° 3).

1О;1

Далее пары ь,) где Ь; Е (bsbebbs) заменяются на двоичный набор из матрицы В„ если (b,b,Ú,,Ье)

50 ется строкой матрицы В, (или из матрицы В2, если (Ь„Ь,,Ь „Ь, ) является строкой матрицы В ) с номером а., если Ь- = О и íà его инверсию, если

b; = 1. Например, если а (3,3,3, 3), (Ъ,Ь,Ь,Ь ) = 1000), тогда (, ) заменяется на (1110), (з ) за"

00011011

00101101

01010101

01100011

01111000

1108618

1010

1011

0110

1100

1001

1101

1110

11111111

Таблица 3

Группа из четырех символов на входе

Соответствующий прямой выход

Принадлежит В

Принадлежит В2

Таблица 2

00

0111

00

0100

Та блица 4

1011

45

0101

1010

0000

0010

1101

0011

5S

0111

1100

О 100

0001

1011000 t

11001001

11100100

С входных шин принятое шестнадцатиразрядное слово поступает в параллельном виде в преобразователь

1 принятого слова, где оно преобразуется таким образом, что каждой группе из четырех последовательных символов принятого слова ставится в соответствце символ кода Рида-Соломона, представленный двумя двоичнычи символами (Π— ОО, 1 — 01, 2 †10, 3 - 11) в соответствии с табл.2.

Продолжение таблицы.2

Одновременно кодовое слово поступает на дешифратор 2, который разбивает принятое слово на четыре последовательные группы по четыре символа в каждой и определяет к какому подмножеству (В„ или В ) двоичного кода принадлежит каждая группа из четырех символов принятого слова. Дешифратор

2 работает в соответствии с табл.3

Дешифратор 2 имеет четыре прямых выхода и четыре инверсных, причем сигнал с прямых и инверсных выходов цешифратора 2 поступает на соответ35 ствующие входы первого блока 14 элементов И. С прямых выходов дешифратора 2 сигнал поступает также на входы обнаружителя 3 ошибок, который определяет к какому из двух возмож40 ных классов ошибок принадлежит принятое слово. Обнаружитель 3 ошибок работает в соответствии с табл.4.

1108618

Продолжение таблицы 4

1011

1101

0001

0011

0101

1001

Если на прямом выходе обнаружителя 3 ошибок появляется сигнал "1", то значит определен первый класс ошибок, соответствующий двум ошибкам в пределах одной группы из четырех символов, или одной ошибке, или отсутствию ошибок. Если на ин35 версном выходе обнаружителя 3 ошибок появляется сигнал "1", то значит определен второй класс ошибок, соответствующий двум ошибкам в пределах разных групп из четырех символов. 40

Декодирование начинается по стартовому сигналу, который поступает на один из входов первого блока 9 управления и второго блока 11 управления и устанавливает пятиразрядный счет45 чик 4 и четырехразрядный счетчик 6 в нулевое состояние. Тактовые импульсы с тактового генератора 10 поступают через первый блок 9 управ-ления на первый вход четырехразрядного счетчика 6, с выхода каждого из четырех разрядов которого сигнал подается на вход кодера 7 кода Рида-Соломона, на первые четыре входа кодера 5 кода (16,8) и на выходные шины. Сигналы с выходов кодера 7

Рида-Соломона и с выходов преобразователя 1 принятого слова подаются на блок 8 сравнения, с выходов которого сигнал подается на второй пороговый элемент 16 с порогом единицы и на соответствующие входы первого блока 14 элементов И. При оп» ределении первого класса ошибок де- кодирование производится за два шага (один шаг требует не более шестнадцати тактов). На первом шаге с прямого выхода обнаружителя 3 ошибок выдается сигнал разрешения на первый элемент И 19, а при срабатывании второго порогового элемента 16 сигнал с его выхода поступает через первый элемент И 19 и элемент ИЛИ 22 в первый блок- 9 управления, который формирует сигнал, прекращающий подачу тактовых импульсов на первый вход четырехразрядного счетчика 6 и выдает сигнал разрешения счета во второй блок 11 управления.

Таким образом, на первом шаге в четырехразрядном счетчике 6 фиксируются четыре разряда и выдаются на выходные шины в качестве первых четырех информационных символов кода (16,8). На втором шаге определяются оставшиеся четыре информационных символа. При этом тактовые импульсы с тактового генератора

10 поступают во второй блок il управления, откуда по сигналу разрешения счета, пришедшего из первого блока

9 управления, подаются на первый вход пятиразрядного счетчика 4. С выходов четырех разрядов пятиразрядного счетчика 4 сигнал подается на вторые четыре входа кодера 5 кода (16,8), при этом на первые четыре входа кодера 5 кода (16,8) по" даются фиксированные сигналы с выходов 4етырехразрядного счетчика 6.

В блоке 13 поразрядного сравнения, содержащем шестнадцать двувходовых сумматоров по модулю два, происходит сравнение принятого слова с последовательно перебираемыми словами кода (16,8). Результат сравнения поступает на входы первого порогового элемента 12 с порогом два. При срабатывании первого порогового элемента 12 с его выхода вьдается сигнал, поступающий во второй блок 11 управления, который формирует сигнал, прекращающий подачу тактовых импульсов, на первый вход пятиразрядного счетчика 4. Таким образом, на втором шаге в пятиразрядном счетчике 4 фиксируются четыре разряда и выдаются на выходные шины в каf3

1108618

14 честве вторых четырех информационных символов кода (16,8). Для деко« дирования требуется от двух до тридцати двух тактов.

При определении второго класса ошибок на первом шаге с инверсного выхода обнаружителя 3 ошибок выдается сигнал разрешения на первые входы второго и третьего элементов И 20, 2 1, а при срабатывании одного из элементов ИЛИ-НЕ 17, 18 сигнал с их выходов поступает через второй и третий элементы И 20, 21 и элемент ИЛИ 22 в первый блок 9 управления, который формирует сигнал, прекращающий подачу тактовых импульсов на вход четырехраэрядного счетчика 6 и выдает сигнал разрешения счета на второй блок 11 управления.

Второй шаг декодирования или совпадает с вторым шагом при определении первого класса ошибок и тогда декодирование заканчивается, или не совпадает, и декодирование не заканчивается. При этом четыре разряда пятираэрядного счетчика 4 переполняются и устанавливаются в нуль, а срабатывает пятый разряд пятиразрядного счетчика 4. С пятого разряда пятиразрядного счетчика 4 сигнал

I поступает во второй блок 11 управления, который формирует сигнал, прекращающий подачу тактовых импульсов на первый вход пятиразрядного счет5 чика 4 и в первый блок 9 управления, который формирует сигнал, разрешающий подачу тактовых импульсов на первый вход четырехразрядного счетчика 6, который продолжает дальнейший счет,.при этом производится третий шаг декодирования, совпадающий с первым шагом при определении втор го класса ошибок. Четвертый шаг декодирования совпадает с вторым шагок при определении первого класса ошибок. Таким образом, декодирование заканчивается на четвертом шаге, при этом требуется максимум сорок восемь тактов, а в прототипе—

256 тактов.

Таким образом, предложенный способ декодирования нелинейного кода обеспечивает более простое дека

25 дирование нелинейного кода,обеспечивает более простое декодирование нелинейного кода (16,8), а устройство, реализующее этот способ, обеспечивает сокращение времени декодирования.

1108618

Выивдыие ширм

1108618

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

Текред Т.Дубинчак Корректор В. Бутяга

Редактор Н. Швьщкая

Тираж 635 Подписное

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

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

Заказ 5885/43

Филиал ППП "Патент", r. Ужгород, ул. Проектная,4