Способ декодирования нелинейного кода и устройство для его осуществления Советский патент 1984 года по МПК H03M13/51 H04L17/30 

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

18

1

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

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

1

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

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

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

Известно устройство, реализующее способ декодирования корректирующих кодов, содержащее корреляционный детектор, первичный детектор, а также синхронизатор и логи1еский блок, к входам которого подЭ1ключены выходы детекторов и синхронизатора 11 . Однако известное устройство имеет большое время декодирования. Наиболее близким к изобретению является способ декодирования нелинейного кода (16,8), представляемого в виде каскадного кода, состоящего из четверичного кода Рида-Соломона и двоичного кода, основанный на поразрядном сравнении принятого слов с кодовыми словами и определении ближайшего от принятого слова по расстоянию Хэмминга, причем принятое слово сравнивают со всеми возможными словами С23, Недостатком известного способа яв ляется сложность декодирования, обус ловленная максимальным числом операций . Известно устройство, реализующее способ декодирования нелинейного код содержащее тактовьп1 генератор и пос- ледовательно соединенные кодер кода (16,8), блок поразрядного сравнения и первый пороговый злемент, причем вторая группа входов блока поразрядного сравнения является входом устройства С 2. Однако известное устройство обладает большим временем декодирования. Цель изобретения - упрощение деко дирования и сокращение времени декодирования . Указанная цель достигается тем, что согласно способу декодирования нелинейного кода (16,8), представляемого в виде каскадного кода, состоящего из четверичного кода Рида-Со ломона и двоичного кода, основанному на поразрядном сравнении принятого слова с кодовыми словами и определении ближайшего от принятого слова по расстоянию Хэмминга, принятое слово разбивают на четыре группы по четыре символа в каждой, преобразуют в кодовые слова кода Рида-Соломона в соответствии с его порождающей матрицей, сравнивают каждую группу из четырех символов с каждой из групп из четырех символов первого и второго подмножества двоичного кода, при совпадении каждой из трех или четырех групп из четырех символов каждая с одной из групп символов тол ко первого или только второго подмножества двоичного кода декодирование осуществляют в два зтапа, причем на первом зтапе сравнивают пре8 4 эбразование из принятого слова кода (16,8) кодовое слово Рида-Соломона . с последовательно перебираемыми кодовыми словами кода Рида-Саломоиа, сформированными из первых четырех информационных символов кода (16,8), причем при расстоянии Хэмминга между сравниваемыми словами нуль или единица запоминают первые четыре информа1хионных символа кода (16,8), а на втором зтапе поразрядно сравнивают принятое слово с последовательно перебираемыми словами кода (16,8) при неизменных первых четырех информационньпс символах кода (16,8), причем при расстоянии Хэмминга мезкду сравниваемыми словами нуль, один или два запоминают вторые четыре информационных символа и заканчивают декодирование, а при совпадении каждой из двух групп из четырех символов каждая с одной из групп символов только первого или только второго подмножества двоичного кода осуществляют операции первого и второго этапов, причем на первом этапе первые четыре информационных символа кода (16,8) запоминают при совпадении двух из четырех символов, взятых из первого подмножества в сравниваемых словах, и заканчивают декодирование, а в случае несоответствия на втором этапе сравнения по расстоянию Хэмминга нуль, один или два повторяют операции для первого и второго этапов, причем на первом этапе четыре информационных символа кода (16,8) запоминают при совпадении двух из четырех символов, взятых из второго подмножества в сравниваемых словах, и заканчивают декодирование. При этом в устройство для декодирования нелинейного кода (16,8), содержащее тактовый генератор и последовательно соединенные кодер ко- . да (16,8), блок поразрядного сравнения и первый пороговый элемент, причем вторая группа входов блока поразрядного сравнения является выходами устройства, введены последовательно соединенные преобразователь принятого слова, блок сравнения и второй пороговый элемент, а также два блока управления, два блока элементов И, два элемента ИЛИ-НЕ, три элемента И, элемент ИЛИ, четьфехразрядный счетчик, кодер Рида-Соломона, обнаружитель i ошибок и дешифратор, входы которого объединены с входами преобразователя принятого слова и второй группой входов блока поразрядного сравнения, при этом выходы блока сравнения подключены к первым входам первого и второго блоков элементов И, причем инверсные входы дешиф ратора подключены к вторым входам первого блока элементов И, а прямые выходы дешифратора подключены к вторым входам второго блока элементов И и к входам обнаружителя ошибок, прямой выход которого подключен к первому входу первого элемента И, а инверсный выход обнаружи теля ошибок подключен к первым входам второго и третьего элементов И, выходы которых подключены к первому и второму входам элемента ИЛИ, к третьему входу которого подключен выход первого элемента И, к второму входу которого подключен выход второ го порогового элемента, при этом выходы первого и второго блоков эле ментов И подключены соответственно к входам первого и второго элементов ИЛИ-НЕ, выходы которых подключе соответственно к вторым входам втор го и третьего элементов И, при этом выходы четырехразрядного счетчика являются выходами устройства и подключены к первой группе входов кодера кода (16,8) и входам кодера Рида-СолОМОНа, выходы которого подключены к второй группе входов блока сравнения, выходы пятиразрядного счетчика являются выходами устройст и подключены к второй группе входов кодера кода (16,8), выход тактового генератора подключен к первым входам первого и второго блоков управления причем первый выход первого блока управления подключен к первому входу четырехразрядного счетчика, а выход второго блока управления подключен к первому входу пятиразрядного счетчика, пятый разряд которого подключен к вторым входам первого и второго блоков управления, выход элемента ИЛИ подключен к третьему входу первого блока управления, а к третьему входу второго 86 блока управления подключен выход первого порогового элемента, а четвертые входы первого и второго блоков управления и вторые входы пятиразрядного и четырехразрядного счетчиков являются входом стартового сигнала, а второй выход первого блока управления подключен к пятому входу второго блока управления. На фиг.1 представлена структурная электрическая схема устройства декодирования нелинейного кода; на фиг.2 - то же, кодера кода Рида-Соломона; на фиг.З - то же, блока сравнения . Устройство для декодирования нелинейного кода содержит преобразователь 1 принятого слова, дешифратор 2, обнаружитель 3 ошибок, пятиразрядный счетчик 4, кодер 5 кода (16,8), четырехразрядный счетчик 6, кодер 7 кода Рида-Соломона, блок 8 сравнения, первый блок 9 управления,тактовый генератор 10, второй блок 11 управления, первьй пороговый элемент 12, блок 13 поразрядного сравнения, первый 14 и второй 15 блоки элементов И, второй пороговьй элемент 16, первый 17 и второй 18 элементы ИЛИ-НЕ, первый 19, второй 20 и третий 21 элементы И, элемент ИЛИ 22. Кодер 7 кода Рида-Соомона содержит сумматоры 23-1-23-6 по модулю два, блок 8 сравнения соержит сумматоры 24-1-24-8 по моулю два элементы ИЛИ 25-1-25-4. Предложенный способ основан а каскадном представлении кода (16,8) в виде четверичного (4,2) ода Рида-Соломона с расстоянием 3 и двоичного кода с расстояием d 2. Порождающая матрица G кода ида-Соломона имеет вид Матрица А кода Рида-Соломона, остоящая из кодовых слов а (), а ,1,2,3}, запиывается в виде

Двоичный код состоит из всевозможных двоичных наборов b (b bjbjb) ,1} длины 4, разбитых на два подмножества В и В,.

номера

омера

а О

1111 0101

1 2 3 0011 0110 0000 1010 1100 1001

Код (16,8) строится следующим образом. Пусть имеются информационные символы (Ь jbjjbjjb ,bj ,bj ,b ,bj ) , b e 0, В соответствии с матрицей G производится кодирование части информационных символов (.Ь) в кодовый вектор а кода Рида-Соломона, а (а,а ,а,а), ,1,2,3} Дaлee пары (ь1 где bi е заменяются на двоичный набор из матрицы В если (Ь,bj,b,,bj) является строкой матрицы В (или из матрицы В,, если (Ь5 ,Ь ,b,bj) является строкой матрицы В) с номером а, если Ь О и на его инверсию, если Ь 1. Например, если а « (3,3,3, 3), (bs.bj.b.bg) 1000), тогда

( ) заменяется на (1110), ( д) за00001111 2222 3333

0123 1032 2301 3210

0231 1320 2013 3102

0312 1203 2130 3021

меняется на (0001) и кодовый вектор запишется в виде (1110 0001 0001 0001)...

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

Сумматоры 23-1-23-6 по модулю

о 1 два в блоке В сравнения соединены в соответствии с табл.1

2 3

Таблица 1

35

91108618

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

С входных шин принятое шестнадцатиразрядное слово поступает в параллельном виде в преобразователь 1 принятого слова, где оно преобразуется таким образом, что каждой группе из четырех последовательных символов принятого слова ставится в соответствие символ кода Рида-Соломона, представленный двумя двоичНЫ4И символами (, , , ) в соответствии с табл.2.

Таблица 2

1000

00

0111

00

1111

00

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

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

Таблица

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

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

Т а б л и ц а 4

О таблицы Продолжение Если на прямом выходе обнаружителя 3 ошибок появляется сигнал 1 то значит определен первый класс ошибок, соответствующий двум ошибкам в пределах одной группы из четырех символов, или одной ошибке, или отсутствию ошибок. Если на инверсном выходе обнаружителя 3 ошибо появляется сигнал 1, то значит оп ределен второй класс ошибок, соответствующий двум ошибкам в пределах разных групп из четырех символов. Декодирование начинается по стартовому сигналу, который поступает на один из входов первого блока 9 упра ления и второго блока 11 управления и устанавливает пятиразрядный счетчик 4 и четырехразрядный счетчик 6 в нулевое состояние. Тактовые импульсы с тактового генератора 10 поступают через первый блок 9 управ ления на первый вход четырехразрядного счетчика 6, с выхода каждого из четырех разрядов которого сигнал подается на вход кодера 7 кода Рида-Соломона, на первые четыре входа кодера 5 кода (16,8) и на выходные шины. Сигналы с выходов кодера 7 Рида-Соломона и с выходов преобразователя 1 принятого слова подаются на блок 8 сравнения, с выходов ко 1 8 торого сигнал подается на второй пороговьй злемеит 16 с порогом единицы и на соответствуюп1ие входы первого блока 14 элементов И. При оп- ределении первого класса ошибок декодирование производится за два inara (один шаг требует не более шестнадцати тактов). На первом шаге с прямого выхода обнаружителя 3 ошибок вьдается сигнал разрешения на первый злемент И 19, а при срабатывании второго порогового элемента 16 сигнал с его выхода поступает через первый элемент И 19 и элемент ИЛИ 22 в первьп блок 9 управления, который формирует сигнал, прекращающий подачу тактовых импульсов на первый вход четьфехразрядного счетчика 6 и вьщает сигнал разрешения счета во второй блок 11 управления. Таким образом, на первом шаге в четырехразрядном счетчике 6 фиксируются четыре разряда и вьщаются на выходные шины в качестве первых четырех информационных символов кода (16,8). На втором шаге определяются оставшиеся четыре информационных символа. При этом тактовые импульсы с тактового генератора 10 поступают во второй блок 11 управления, откуда по сигналу разрешения счета, пришедшего из первого блока 9 управления, подаются на первый вход пятиразрядного счетчика 4. С выходов четьфех разрядов пятиразрядного счетчика 4 сигнал подается на вторые четыре входа кодера 5 кода (16,8), при этом на первые четьфе входа кодера 5 кода (16,8) подаются фиксированные сигналы с выходов г етьфехразрядного счетчика 6. В блоке 13 поразрядного сравнения, содержащем шестнадцать двувходовых сумматоров по модулю два, происходит сравнение принятого слова с последовательно перебираемыми словами кода (16,8). Результат сравнения поступает на входы первого порогового элемента 12 с порогом два. При срабатьшании первого порогового элемента 12 с его выхода выдается сиг-, нал, поступающий во второй блок 11 управления, который формирует сигнал, прекращающий подачу тактовьж импульсов, на первый вход пятиразрядного счетчика 4. Таким образом, на втором шаге в пятиразрядном счетчике 4 фиксируются четыре разряда и выдаются на выходные шины в качестве вторых четырех информационных символов кода (16,8). ,Цпя декодирования требуется от двух до трид цати двух тактов. При определении второго класса ошибок на первом шаге с инверсного выхода обнаружителя 3 ошибок вьдается сигнал разрешения на первые входы второго и третьего элементов И 20, 21, а при срабатьгоании одного из элементов ИЛИ-НЕ 17, 18 сигнал с их выходов поступает через второй и третий элементы И 20, 21 и элемент ИЛИ 22 в первый блок 9 уп равления, который формирует сигнал, прекращающий подачу тактовых импуль сов на вход четырехразрядного счетчика 6 и выдает сигнал разрешения счета на второй блок 11 управления. Второй шаг декодирования или совпадает с вторым шагом при определении первого класса ошибок и тогда декодирование заканчивается, или не совпадает, и декодирование не заканчивается. При этом четьфе разряд пятиразрядного счетчика А переполняются и устанавливаются в нуль, а срабатывает пятьй разряд пятиразрядного счетчика 4. С пятого разряд пятиразрядного счетчика 4 сигнал 1 поступает во второй блок 11 управления, который формирует сигнал, прекращающий подачу тактовых импульсов на первый вход пятиразрядного счетчика 4 и в первый блок 9 управления, который формирует сигнал, разрешающий подачу тактовых импульсов на первый вход четырехразрядного счетчика 6, который продолжает дальнейший счет,, при зтом производится тре тий шаг декодирования, совпадающий с первым шагом при определении BTopi го класса ошибок. Четвертый пнг декодирования совпадает с вторым шагок при определении первого класса ошибок. Таким образом, декодирование заканчивается на четвертом шаге, при этом требуется максимум сорок восемь тактов, а в прототипе 256 тактов. Таким образом, предложенный способ декодирования нелинейного кода обеспечивает более простое деко дирование нелинейного кода обеспечивает более простое декодирование нелинейного кода (16,8), а устройство, реализующее этот способ, обеспечивает сокращение времени декодирования.

HID

a

titoi cmapmotett -

I

H.

ц t,,,

ilJ

w

hs

17

ya

18

0utl

фие.2