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

СОЮЗ СОВЕТСКИХШИВФРНЕСННЖРЕСПУБЛИК 13/32 за 1 Н.04 10. Н ИСАНИЕ ИЗОБРЕТЕНИЯ ЬН 4 ИОТЫЛ ИДВТОЪСТВУ АВТОРСКОМУ СВ Тузи 1941,др. Теорики. М.,(прототип ГОСУДАРСТОЕННЫЙ КОМИТЕТ ССПО ДЕЛАМ ИЗОБРЕТЕНИЙ И (ЛНРЫТИ(54) СПОСОБ ДЕКОДИРОВАНИЯ НЕЛИНЕЙНОГО КОДА И УСТРОЙСТВО ДЛЯ ЕГО ОСУЩЕСТВЛЕНИЯ,(57) 1, Способ декодирования нелинейного кода (16,8), представляемого в виде каскадного кода, состоящего иэ четверичного кода Рида-Со.ломона и двоичного кода, основанныйна поразрядном сравнении принятогослова с кодовыми словами и определении ближайшего от принятого словапо расстоянию Хэмминга о т л и ч а ю.щ и й с я тем, что, с целью упрощения декодирования, принятое словоразбивают на четыре группы по четыресимвола в каждой, преобразуют в кодовые слова кода Рида-Соломона всоответствии с его порождающей матрицей, сравнивают каждую группу изчетырех символов с каждой из группиз четырех символов первого и второго подмножества двоичного кода,при совпадении каждой из трех иличетырех групп из четырех символовкаждая с одной из групп символовтолько первого нли только второгоподмножества двоичного кода декодирование осуществляют в два этапа,причем на первом этапе сравнивают преобразованное иэ принятого слова кода ( 16,8) кодовое слово Рида-Соло" мона с последовательно перебираемыми кодовыми словами кода Рида-Соломона, сформированными из первых четырех информационных символов кода (16,8), причем при расстоянии Хэмминга между сравниваемыми словами нуль или единица запоминают первые четыре информационных символа . кода(16,8),а на втором этапе поразрядно сравнивают принятое слово с последовательно перебираемыми словами кода (16,8) при неизменных первых четырех информационных символах кода (16,8),причем при расстоянииХэмминга между сравниваемыми словами нуль, один или два запоминают вторые четыре информационных символа и заканчивают декодирование, а при совпадении каждой нз двух групп из четырех символов каждая с одной изФ групп символов только первого или только второго подмножества двоичного кода осуществляют операции первого и второго этапов, причем на1 первом этапе первые четыре информационных символа кода (16,8) запоминают при совпадении двух иэ четырех символов, взятых из первого подмножества в сравниваемых словах, и заканчивают декодирование, а в случае несоответствия на втором этапе сравнения по расстоянию Хэмминга нуль, один или два повторяют операции для первого и второго этапов, причем на первом этапе четыре информационных символа кода (16,8) запоминают при совпадении двух иэ четырех символов, взятых из второго подмножества в сравниваемых словах, и заканчивают декодирование,1108618 Составитель С. Осмоловский Техред Т.Дубинчак Корректор В. Бутяга Редактор Н, Швьщкая Тираж 635 Подписное ВНИИПИ Государственного комитета СССР по делам изобретений и открытий 113035, Москва, Ж, Раушская наб., д. 4/5112. Устройство для декодирования нелинейного кода (16,8), содержащее тактовый генератор и последовательно соединенные кодер кода (16,8),блок поразрядного сравнения и первый пороговый элемент, причем вторая группа входов блока поразрядного сравнения является выходами устройства, о т л и ч а ю щ е е с я тем, что с целью сокращения времени декодирования, введены последовательно соединенные преобразователь принятого слова, блок сравнения и второй пороговый элемент, а также два блока управления, два блока элементов И, два элемента ИЛИ-НЕ, три элемента И, элемент ИЛИ, четырехразрядный счетчик, нятираэрядный счетчик, кодер Рида-Соломона, обнаружитель ошибок и дешифратор, входы которого объединены с входами преобразователя принятого слова и второй группой входов блока поразрядного сравнения, нри этом выходы блока сравнения подключены к первым входам первого и второго блоков элементов И, причем инверсные входы дешифратора подключены к вторым входам первого блока элементов И, а прямые выходы дешифратора подключены к вторым входам второго блока элементов И и к входам обнаружителя ошибок, прямой выход которого подкйючен к первому входу первого элемента И, а инверсный выход обнаружителя ошибок подключен к первым входам второго и третьего элементов И, выходы которых подключены к первому и второму входам элемента ИЛИ, к третьему входу которого подключен выход первого элемента И, к второму 08618входу которого подключен выход второго порогового элемента, при этом выходы первого и второго блоков элементов И подключены соответственно к входам первого и второго элементов ИЛИ-НЕ, выходы которых подключены соответственно к вторым входам второго и третьего элементов И, при этом выходы четырехразрядного счетчика являются выходами устройства и подключены к первой группе входов кодера кода (16,8) и входам кодера Рида-Соломона, выходы которого подключены к второй группе выходов блока сравнения, выходы пятиразрядного счетчика являются выходами устройства и подключены к второй группе входов кодера кода (16,8), выход тактового генератора подключен к первым входам первого и второго блоков управления, причем первый выход первого блока управления подключен к первому входу четырехразрядного счетчика, а выход второго блока управления подключен к первому входу пятиразрядного счетчика, пятый разряд которого подключен к вторым входам первого и второго блоков управления, выход элемента ИЛИ подключен к третьему входу первого блока управления, а к третьему входу второго блока управления подключен выход первого порогового элемента, а четвертые входы первого и второго блоков управления и вторые входы пятиразрядного и четырехразрядного счетчиков являются входом стартового сигнала, а второй выход первого блока управления подключен к пятому входу второго блока управления.Изобретение относится к технике передачи данных и к вычислительной технике и может найти применение для повьппения достоверности при передаче и хранении информации. 5Известен способ декодирования корректирующих кодов, заключающийся в том, что принятые слова сравниваются с возможными кодовыми словами, по результатам сравнения выбирается слово с наилучшей корреляцией 111,2Однако, известный способ предназначен для декодирования широкого класса кодов и поэтому для конкретного кода (16,8) требует большое количество операций.Известно устройство, реализующее споСоб декодирования корректирующих кодов, содержащее корреляционный детектор, первичный детектор, а также синхронизатор и логический блок, к входам которого под618 Э 1108 ключены выходы детекторов и синхронизатора 11 3.Однако известное устройство имеет большое время декодирования.Наиболее близким к изобретению 5 является способ декодирования нелинейного кода (16,8), представляемого в виде каскадного кода, состоящего из четверичного кода Рида-Соломона и двоичного кода, основанный на ОФпоразрядном сравнении принятого слова с кодовыми словами и определении ближайшего от принятого слова по расстоянию Хэмминга, причем принятое слово сравнивают со всеми возможными 15 словами 23.Недостатком известного способа является сложность декодирования, обусловленная максимальным числом операций. 20Известно устройство, реализующее способ декодирования нелинейного кода1 содержащее тактовый генератор и пос - ледовательно соединенные кодер кода (16,8), блок поразрядного сравнения 25 и первый пороговый элемент, причем вторая группа входов блока поразрядного сравнения является входом устройства 23.Однако известное устройство обла дает большим временем декодирования.Цель изобретения - упрощение декодирования и сокращение времени декодирования.Указанная цель достигается темф 35 что согласно способу декодированиянелинейного кода (16,8), представляемого в виде каскадного кода, состоящего из четверичного кода Рида-Соломона и двоичного кода основанномуУ 40 на поразрядном сравнении принятого слова с кодовыми словами и определении ближайшего от принятого слова по расстоянию Хэмминга, принятое слово разбивают на четыре группы по 45 четыре символа в каждой, преобразуют в кодовые слова кода Рида-Соломона в соответствии с его порождающей матрицей, сравнивают каждую группу, из четырех символов с каждой из 50групп из четырех символов первого ивторого подмножества двоичного кода,при совпадении каядой из трех иличетырех групп из четырех символовкаждая с одной из групп символов толь.ко первого или только второго под 55 множества двоичного кода декодирование осуществляют в два этапа причем на первом этапе сравнивают преобразование из принятого слова кода (16,8) кодовое слово Рида-Соломона с последовательно перебираемыми кодовыми словами кода Рида-Соломона, сформированными из первых четырех информационных символов кода (16,8), причем при расстоянии Хэмминга между сравниваемыми словами нуль или единица запоминают первые четыре информационных символа кода (16,8), а на втором этапе поразрядно сравни" вают принятое слово с последовательно перебираемыми словами кода (16,8) при неизменных первых четырех информационных символах кода (16,8), причем при расстоянии Хэмминга между сравниваемыми словами нуль, один или два запоминают вторь 1 е четыре информационных символа и заканчивают декодирование, а при совпадении каядой из двух групп из четырех символов каядая с одной из групп символов только первого или только второго подмножества двоичного кода осуществляют операции первого и второго этапов, причем на первом этапе первые четыре информационных символа кода (16,8) запоминают при совпадении двух из четырех символов, взятых из первого подмножества в сравниваемых словах, и заканчивают декодирование, а в случае несоответствия на втором этапе сравнения по расстоянию Хэмминга нуль, один или два повторяют операции для первого и второго этапов, причем на первом этапе четыре информационных символа кода (16,8) запоминают при совпадении двух иэ четырех символов, взятых из второго подмножества в сравниваемых словах, и заканчивают декодирование.При этом в устройство для декодирования нелинейного кода (16,8), содержащее тактовый генератор и последовательно соединенные кодер кода (16,8), блок поразрядного сравнения и первый пороговый элемент, причем вторая группа входов блока поразрядного сравнения является выходами устройства, введены последовательно соединенные преобразователь принятого слова, блок сравнения и второй пороговый элемент, а также два блока управления, два блока элементов И, два элемента ИЛИ-НЕ, три элемента И, элемент ИЛИ, четырехразрядный счетчик, кодер Рида-Соломона, обнаружитель5 11086 ошибок и дешифратор, входы которого объединены с входами преобразователя принятого слова и второй группой входов блока поразрядного сравнения, при этом выходы блока сравнения подключены к первым входам первого и второго блоков элементов И, причем инверсные входы дешифратора подключены к вторым входам первого блока элементов И, а прямые 10 выходы дешифратора подключены к вторым входам второго блока элементов И и к входам обнаружителя ошибок, прямой выход которого подключен к первому входу первого элемента И, а инверсный выход обнаружителя ошибок подключен к первым входам второго и третьего элементов И, выходы которых подключены к первому и второму входам элемента ИЛИ, к третьему входу которого подключен выход первого элемента И, к второму входу которого подключен выход второго порогового элемента, при этом выходы первого и второго блоков элементов И подключены соответственно к входам первого и второго элементов ИЛИ-НЕ, выходы которых подключены соответственно к вторым входам второго и третьего элементов И, при этом выходы четырехразрядного счетчика являются выходами устройства и подключены к первой группе входов кодера кода (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 элементы ИЛИ-НЕ, первый 19, второй 20и третий 21 элементы И, элемент ИЛИ 22. Кодер 7 кода Рида-Соломона содержит сумматоры 23-1-23-6 по модулю два, блок 8 сравнения содержит сумматоры 24-1-24-8 по модулю два элементы ИЛИ 25-1-25-4.Предложенный способ основанна каскадном представлении кода(16,8) в виде четверичного (4,2) кода Рида-Соломона с расстояниемгг = 3 и двоичного кода с расстоянием г 1 = 2.Порождающая матрица С кодаРида-Соломона имеет вид0132Матрица А кода Рида-Соломона, состоящая из кодовых слов а1108618 оооо 1111 2222 3333 0123 1032 2301 3210 0231 1320 2013 3102 О 312 1203 2130 3021 меняется на (0001) и кодовый вектор 25 запишется в виде (1110 0001 00010001) .Устройство для декодирования нелинейного кода работает следующимобразом.зо Сумматоры 23-1-23-6 по модулюдва в блоке 8 сравнения соединеныв соответствии с табл.1 состоит из всевознаборов ЬЕ0,1 длины 4, подмножества В, и Двоичный код можных двоичных 1 2 3 4 разбитых на дваа, 0 1 2 3 1111 0101 0011 0110 0000 1010 1100 1001 1000 0100 0010 0001 0111 1011 1101 1110 Та бли ца 1 Вг 35 В1 Входы Выходы 00000000 0000 0001 0010 0011 0100 0101 0110 0111 1000 10000111 10011100 1001 Код (16,8) строится следующим об разом. Пусть имеются информационные символы (Ь,Ь,Ъз,Ь 4,Ь ,Ьь,Ь,Ъ ), Ъ; е 0,1 В соответствии с матрицей С производится кодирование части информационных символов (Ь,ЪЬ Ь ) 45 в кодовый вектор а кода Рида-Соломона, а = (а,а ,а ,а ), а;60,1,23)1011Далее пары ь,) где Ь; Е 1 Ь Ъ Ъ,Ь ) заменяются на двоичный набор из матрицы В если (Ь ,Ь ,ЪЬ ) явля 50 ется строкой матрицы В, (или из матрицы В , если (Ь ,Ь ,ЬЬ ) является строкой матрицы В) с номером а., если Ь. = 0 и на его инверсию, если1Ь, = 1. Например, если а (3,3,3, 3), (Ъ,Ь,ЬЬ ) = 1000), тогда ( 1 ) заменяется на (1110), ( з ) за" 00011011 00101101 00110110 01001110 01010101 01100011 011110009 10 1108618 1010 1011 0110 1100 1001 10 1101 1110 11111111 Таблица 3 Группа из четырех символов на входе Соответствующийпрямой выход 25 Принадлежит В 1 Принадлежит В 2 Таблица 2 30 00 0111 00 00 0000 0100 00 01 Та блица 4 1011 01 45 0101с 01 1010 01 0000 0010 10 1101 10 0011 1000 0111 10 1100 10 0100 0001 10101010 10110001 11001001 11010010 11100100 С входных шин принятое шестнадцатиразрядное слово поступает в па-раллельном виде в преобразователь 1 принятого слова, где оно преобразуется таким образом, что каждой группе из четырех последовательных символов принятого слова ставится в соответствце символ кода Рида-Соломона, представленный двумя двоичньии символами (О -ОО, 1 - 4 01, 2 - 10, 3 -11) в соответствии с табл.2. Продолжение таблицы,2 Одновременно кодовое слово поступает на дешифратор 2, который разбивает принятое слово на четыре последовательные группы по четыре символа в каждой и определяет к какому подмножеству (В или В ) двоичного кода принадлежит каждая группа из четырех символов принятого слова. Дешифратор 2 работает в соответствии с табл.3 Дешифратор 2 имеет четыре прямыхвыхода и четыре инверсных, причемсигнал с прямых и инверсных выходовцешифратора 2 поступает на соответ ствующие входы первого блока 14 элементов И. С прямых выходов дешифратора 2 сигнал поступает также навходы обнаружителя 3 ошибок, которыйопределяет к какому из двух возмож ных классов ошибок принадлежит принятое слово. Обнаружитель 3 ошибокработает в соответствии с табл.4.Продолжение таблицы 4010 110101 0011 1 ОО001 0110Если на прямом выходе обнаружителя 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). На втором шаге определяются оставшиеся четыре информационных символа. При этом тактовые импульсы с тактового генератора 1 О поступают во второй блок 11 управления, откуда по сигналу разрешения счета, пришедшего из первого блока 9 управления, подаются на первый вход пятиразрядного счетчика 4. С выходов четырех разрядов пятиразрядного счетчика 4 сигнал подается на вторые четыре входа кодера 5 кода (16,8), при этом на первые четыре входа кодера 5 кода (16,8) по" даются фиксированные сигналы с выходов 4 етырехразрядного счетчика 6.В блоке 13 поразрядного сравне" ния, содержащем шестнадцать двувходовых сумматоров по модулю два, происходит сравнение принятого слова с последовательно перебираемыми словами кода (16,8). Результат сравнения поступает на входы первого порогового элемента 12 с порогом два. При срабатывании первого порогового элемента 12 с его выхода вьдается сигнал, поступающий во второй блок 11 управления, который формирует сигнал, прекращающий подачу тактовых импульсов, на первый вход пятиразрядного счетчика 4. Таким образом, на втором шаге в пятиразрядном счетчике 4 фиксируются четыре разряда и выдаются на выходные шины в ка 1108618 14честве вторых четырех информациойных символов кода (16,8), Для деко" дирования требуется от двух до тридцати двух тактов.При определении второго класса ошибок на первом шаге с инверсного выхода обнаружителя 3 ошибок выдается сигнал разрешения на первые входы второго и третьего элементов И 20, 2 1, а при срабатывании одного из элементов ИЛИ-НЕ 17, 18 сигнал с их выходов поступает через второй и третий элементы И 20, 21 и элемент ИЛИ 22 в первый блок 9 управления, который формирует сигнал, прекращающий подачу тактовых импульсов на вход четырехраэрядного счетчика 6 и выдает сигнал разрешения счета на второй блок 11 управления. Второй шаг декодирования или совпадает с вторым шагом при определении первого класса ошибок и тогда декодирование заканчивается, или не совпадает, и декодирование не заканчивается. При этом четыре разряда пятираэрядного счетчика 4 переполняются и устанавливаются в нуль, а срабатывает пятый разряд пятиразрядного счетчика 4. С пятого разряда пятиразрядного счетчика 4 сигнал 1 поступает во второй блок 11 управления, который формирует сигнал, прекращающий подачу тактовых импульсовна первый вход пятиразрядного счет 5 чика 4 и в первый блок 9 управления,который формирует сигнал, разрешающий подачу тактовых импульсов напервый вход четырехразрядного счетчика 6, который продолаает дальнейший счетпри этом производится тре.тий шаг декодирования, совпадающийс первым шагом при определении вторго класса ошибок, Четвертый шаг декодирования совпадает с вторым шагокпри определении первого класса ошибок. Таким образом, декодированиезаканчивается на четвертом шаге,при этом требуется максимум сороквосемь тактов, а в прототипе -20 256 тактов,Таким образом, предложенныйспособ декодирования нелинейногокода обеспечивает более простое дека 25дирование нелинейного кода, обеспечивает более простое декодированиенелинейного кода (16,8), а устрой"ство, реализующее этот способ, обес"печивает сокращение времени декодирования,