СИСТЕМА ДЛЯ КОДИРОВАНИЯ И ДЕКОДИРОВАНИЯ С ИСПРАВЛЕНИЕМ ОШИБОК Российский патент 1994 года по МПК H03M13/02 

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

Известно достаточно большое число помехоустойчивых кодов, исправляющих ошибки. Наиболее мощными современными системами кодирования и декодирования, исправляющими ошибки, являются системы с каскадными кодами. Для исправления t ошибок при правильном выборе кодов первой и второй ступеней каскадный код требует 2t проверочных символов. К недостаткам каскадного кода следует отнести неоднородность и логическую сложность его структуры и большое число многозначных логических элементов в кодере и декодере, обеспечивающих операции в конечном поле Галуа GF(q).

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

Цель достигается следующим способом. Информационные двоичные символы записываются в оперативное запоминающее устройство кодера группами по l - 1 двоичных символов по m - 1 строчкам матрицы размером (m - 1) x (l - 1), где l - простое число, l > m. Матрица дополняется проверками на четность по строкам и по столбцам и превращается в матрицу размером m x l. Символы из такой матрицы считываются по диагонали группами по m символов. Считывание начинается с элемента a_oo, затем номер строки и номер столбца одновременно увеличиваются на единицу, пока не достигается элемент из последней строчки. Группа элементов a_oo, а₁₁, а₂₂, . . . , a_m-1m-1 образует косой ряд. Далее считывание начинается с элемента а₀₁ по такому же правилу, образуя косой ряд a₀₁, a₁₂, . . . , a_m-1m. По достижении последнего столбца его номер берется по модулю l и косой ряд продолжается с нулевого столбца. Порядковый номер считываемого символа n взаимно однозначно связан с номером строки i и номером столбца j соотношением
n = m[(j - 1) mod l] + i, где ( ) mod l - операция вычисления положительного остатка от деления на l. Каждой из этих групп сопоставляется один из 2^m сигналов в канале связи. Декодер принимает информацию группами по m двоичных символов и восстанавливает исходную матрицу из принятых символов. Далее он вычисляет двоичные суммы символов по строкам и по столбцам, образуя векторы из m проверок по строкам и первых m проверок по столбцам. Производится циклический сдвиг принятых символов поблочно по m двоичных символов до тех пор, пока группа из m первых проверок по столбцам не совпадает с вектором проверок по строкам. В случае совпадения эта группа складывается покомпонентно по модулю два с первым блоком из m двоичных символов и ошибки исправляются.

Рассмотрим матрицу информационных символов a_ij размером (m - 1) x (l - 1) и дополним ее проверочными символами на четность b_ij как по строкам, так и по столбцам. Результирующая матрица показана на фиг. 2.1; на фиг. 2.2 показан порядок считывания матрицы при m = 4, l = 5; на фиг. 2,3а приводится матрица, в которой произошли ошибки во втором косом ряду. Изначально матрица содержала только нулевые элементы. Векторы проверочных сумм по столбцам и по строкам не совпадают. После циклического сдвига на одну группу из четырех двоичных символов ошибочный косой ряд попадает на первое место и векторы проверок по строкам и по столбцам совпадают (см. фиг. 2,3б). Если добавить проверочные символы по модулю два к первому косому ряду, ошибки исправятся. Матрица снова станет нулевой. Такой способ кодирования и коррекции ошибок проще известного ранее, что служит достижению цели. Устройство, реализующее данный способ кодирования, состоит из кодера и декодера, схемы которых приведены на фиг. 4, 5 и 6.

Кодер (фиг. 4) состоит из регистра 9 сдвига, в который информация записывается в порядке, указанном в способе, и сумматоров 1-8 по модулю два.

Кодер для кода длиной l символов из алфавита размером 2^m состоит из регистра 9 сдвига с lm ячейками, l сумматоров по модулю два (ИСКЛЮЧАЮЩЕЕ ИЛИ) с m - 1 входами (1, 5, 6, 7, 8) и m - 1 сумматоров по модулю два с l - 1 входами (2, 3, 4). Сумматоры с m - 1 входами подключены к ячейкам последовательного регистра сдвига с номерами k = m [ (j - 1) mod l] + i, где i - номер входа сумматора (i = 0, 1, . . . , m - 2); j - номер сумматора (j = 0, 1, . . . , l - 1). Выходы этих сумматоров подключены к ячейкам последовательного регистра сдвига с номерами k = = m[(j - m + 1) mod l] + m - 1, где j - номер сумматора. Сумматоры с l - 1 входами подключены к ячейкам последовательного регистра сдвига с номерами k = m[(j - 1) mod l] + +i, где i - номер сумматора (i = 0, 1, . . . , m - 2); j - номер входа сумматора (j = 0, 1, . . . , l - 2). Выходы этих сумматоров подключены к ячейкам последовательного регистра сдвига с номерами k = m[(l - 1 - i) mod l] + i, где i - номер сумматора. Информационная шина подключена своими линиями к ячейкам регистра с номерами k = m[(j - 1) mod l] + i, где i = 0, 1, . . . , m - 2; j = 0, 1, . . . , l - 2.

Последовательный выход регистра сдвига является выходом кодера. Запись в последовательный регистр сдвига производится импульсом Т2 синхронизации по кодовым группам, совпадающим во времени с приходом информации на вход кодера. Тактируется регистр импульсами синхронизации по битам Т_о. Символы с выходов кодера группами по m символов поступают в модулятор, где им сопоставляются сигналы из ансамбля с 2^m членами. Эти сигналы передаются по каналу связи.

На фиг. 4 приводится принципиальная схема кодера для кода длиной 5 символов из алфавита 2⁴.

Общая схема декодера приводится на фиг. 2.5. Декодер состоит из регистра 10 сдвига, в котором информация хранится в порядке, описанном выше, первого 11 и второго 12 блоков сумматоров (логических цепей, вычисляющих проверочные суммы (синдромы) по столбцам 11 и по строкам 12), блока 13 сравнения, согласующего блока 14, сумматора 15 по модулю два (схемы покомпонентного суммирования по модулю два) и ключа. При этом группа из m двоичных символов, расположенных в косом ряду, начиная с элемента в первой строке, рассматривается как многозначный символ из алфавита 2^m. В регистре сдвига эта группа символов располагается в соседних ячейках.

Для кода длиной l символов из алфавита 2^m регистр 16 последовательного сдвига содержит lm двоичных ячеек и тактируется сигналами синхронизации по битам Т_о.

Первый блок 11 сумматоров, вычисляющий проверочные суммы по столбцам, состоит из m сумматоров 17-20 с m входами. Входы j-го (j = 0, 1, . . . , m - 1) сумматора подключены к ячейкам регистра последовательного сдвига с номерами k = m[(j - 1) mod l] + i, где i - номер входа сумматора (i = 0, 1, . . . , m - 1). Выходы сумматоров являются выходами этой логической цепи.

Второй блок 12 сумматоров, вычисляющий проверочные суммы по строкам, состоит из m сумматоров 21-24 с l входами. Выходы i-го сумматора (i = 0, 1, . . . , m - 1) подключены к ячейкам регистра последовательного сдвига с номерами k = m[(j - 1) mod l] + i, где j - номер входа сумматора (j = 0, 1, . . . , l - 1). Выходы сумматоров являются выходами логической цепи.

Блок 13 сравнения состоит из m сумматоров 25-28 по модулю два с двумя входами, логического элемента ИЛИ-НЕ 29 с m входами и D-триггера 30. Входы i-го сумматора блока сравнения подключены к выходам i-х сумматоров логических схем, вычисляющих проверочные суммы по столбцам и по строкам. Выходы сумматоров 25-28 подключены к входам логического элемента ИЛИ-НЕ 29, выход которого подключен к D-входу D-триггера 30. С-выход этого триггера управляется сигналами символьной синхронизации Т₁, которые следуют каждые m тактов Т_о. Выход D-триггера - выход блока сравнения.

Согласующий блок 14 состоит из регистра 31 последовательного сдвига из m ячеек, логического элемента И 32. Входы ячеек регистра сдвига подключены к выходам соответствующих сумматоров логической схемы, вычисляющей проверочные суммы по строкам (или по столбцам). Выход регистра сдвига подключен к первому входу логического элемента И 32. Второй вход этого элемента подключен к выходу D-триггера 30 блока сравнения. Запись в регистр сдвига производится сигналами Т₁, а тактирование - сигналами Т_о. Выход логического элемента И 32 подключен к двухвходовому сумматору 33 по модулю два. Этот сумматор реализует покомпонентное суммирование. Выход сумматора представляет собой выход всей схемы, а второй его вход подключен в соответствии с общей схемой к выходу регистра 16 последовательного сдвига. Выход регистра через ключ 34 подключен к его входу. Ключ управляется сигналом синхронизации по кодовым группам Т₂ (на общей схеме ключ не выделен).

Декодер работает следующим образом.

Приходящая кодовая комбинация через ключ 34 поступает на вход регистра 16 последовательного сдвига и записывается в него группами по m двоичных символов (косой ряд), рассматриваемых как многозначный символ из алфавита 2^m.

На выходе двоичных сумматоров 17-24 логических цепей, вычисляющих проверочные символы как по строкам, так и по столбцам, образуются потенциалы, соответствующие проверочным символам. Проверки на четность по строкам образуют вектор S1 из m элементов. Проверки по столбцам образуют вектор S2 из m элементов. Проверки на четность в последних столбцах не производятся. Если ошибка содержится в первой группе из m двоичных элементов, расположенных в косом ряду, начиная с первого элемента матрицы, то вектор проверок по столбцам совпадает с вектором проверки по строчкам. Добавляя покомпонентно по модулю два вектор S1 к первой группе из m двоичных символов, ошибку можно исправить. Этот случай соответствует ошибке в первом многозначном символе из алфавита 2^m. Если ошибка произошла в другом многозначном символе (в другой группе из m двоичных символов, расположенных в косом ряду, начиная с элемента в первой строке), то декодер начинает сдвигать в цикле информацию, записанную в регистре, группами по m двоичных чисел (т. е. равно по одному многозначному символу) и сравнивать проверочные векторы S1 и S2. Если S1 = S2, значит ошибочная группа из m двоичных символов оказалась на первом месте и ее можно исправлять, складывая ее покомпонентно по модулю два с проверочным вектором S1 = S2. При циклическом сдвиге информации в регистре группами по m двоичных знаков косые ряды сдвигаются по матрице по кругу. При этом вектор проверок по столбцам сохраняется, а вектор проверок по строкам циклически сдвигается. Если число столбцов простое, то среди l последовательных циклических сдвигов нет ни одной одинаковой пары. Все l сдвигов, соответствующих расположению на первом месте l различных последовательных многозначных символов, различны. Следовательно, такой метод декодирования однозначен.

Такой код исправляет однократный сбой в группе из m двоичных символов или одну ошибку в многозначном символе из алфавита 2^m. Число проверочных символов: две группы по m двоичных знака или два символа из алфавита 2^m. Таким образом, данный способ кодирования на исправление одного многозначного символа тратит два проверочных символа из того же многозначного алфавита. Рассмотренный код эквивалентен лучшим из известных кодов, исправляющих один многозначный символ: многозначному коду Хэмминга с двумя проверочными символами или коду Рида-Соломона также с двумя проверочными символами. По сравнению с этими известными кодами рассмотренный способ кодирования выгодно отличается более простым декодером.

Рассмотренная схема не содержит сложных логических элементов, реализующих умножение и сложение в поле Галуа из 16 элементов. Вместо сложных логических схем умножения и сложения в целочисленном поле Галуа используются схемы ИСКЛЮЧАЮЩЕЕ ИЛИ, два регистра, D-триггер, элемент ИЛИ-НЕ, реализованные в виде стандартных микросхем. Простота реализации и структуры декодера выгодно отличает его от известных аналогов и прототипов. Более простые схемы кодера и декодера позволяют повысить надежность кодера и увеличить быстродействие кодирования и декодирования информации. Предлагаемая система исправляет не только однократные двоичные ошибки, но и сбои целых групп по m двоичных символов, что повышает надежность работы кодера в канале с шумом при передаче информации с помощью многозначных сигналов. (56) Авторское свидетельство СССР N 1109924, кл. H 04 L 1/10, 1983.

Авторское свидетельство СССР N 1358098, кл. H 03 M 13/00, 1985.

Изобретение относится к многозначному помехоустойчивому кодированию для защиты передаваемой по каналу информации от сбоев, вызванных помехами. Задача - создание способа защиты цифровой информации, передаваемой по каналу с помощью многозначного ансамбля сигналов, от сбоев и помех в канале связи. Передаваемые информационные символы записываются в память кодера, реализованную в виде регистра сдвига, по строкам матрицы ml с проверочными символами на четность по столбцам в последней строке и по строкам в последнем столбце. Символы считываются в канал по диагонали так, что порядковый номер считываемых символов связан с номером строки i и номером столбца j соотношением n= m[(j-i)mod 1] +i. По каналу информация передается с помощью 2^m различных сигналов, которым сопоставляются группы из m последовательно расположенных двоичных символов. В декодере принимаемые символы записываются в регистр сдвига и регистр с помощью ключа замыкается в кольцо. С помощью блоков сумматоров вычисляются проверки на четность по строкам и по столбцам, которые сравниаются между собой в блоке сравнения при различных циклических сдвигах принятой последовательности на группы по m двоичных символов. При совпадении проверок они с помощью согласующего блока и сумматора по модулю два складываются с последовательностью информационных символов, исправляя ее от ошибок. 6 ил.

СИСТЕМА ДЛЯ КОДИРОВАНИЯ И ДЕКОДИРОВАНИЯ С ИСПРАВЛЕНИЕМ ОШИБОК состоящая из кодера, выполненного на регистре сдвига, и декодера, содержащего первый и второй блоки сумматоров и сумматор по модулю два, выход которого является выходом декодера, отличающаяся тем, что, с целью повышения надежности системы и ее быстродействия, в кодер введены l сумматоров по модулю два с m - 1 входами (где l - простое число; m - длина многозначного кода с символами из алфавита 2^m), i-й вход j-го сумматора (где о ≅ i < m - 1 и 0 ≅ j < l) объединен с входом k-й ячейки регистра сдвига, где k = m [(j - i)mod l] + i, и является соответствующим информационным входом кодера, а выход подключен к входу k-й ячейки регистра сдвига, где k = m [(j - m + 1)mod l] + m - 1, и m - 1 сумматоров по модулю два с l - 1 входами, r-й вход n-го сумматора (где 0 ≅ r < l - 1, 0 < n < m - 1) объединен с входом k-й ячейки регистра сдвига, где k = m[(r - n)mod l] + n, а выход подключен к входу k-й ячейки регистра сдвига, где k = m[(l - n - 1)modl] + n, и является соответствующим информационным входом устройства, входы d - х ячеек регистра последовательного сдвига, где d = m[(q - p)mod l] + p, 0 < p < m - 1, 0 < q < m - 1, являются информационными входами кодера, тактовый вход, вход записи и выход регистра сдвига являются соответственно тактовым и управляющим входами и выходом кодера, в декодер введены ключ, регистр сдвига, блок сравнения и согласующий блок, первый блок сумматоров выполнен в виде m сумматоров с m входами, y-входы s-х сумматоров первого блока подключены к выходам k-х ячеек регистра сдвига, где k = m[(s - y)mod l] + y, 0 < s < m, 0 < y < m, второй блок сумматоров выполнен в виде m сумматоров с l входами, f-входы g-х сумматоров второго блока (где 0 ≅ f ≅ m, 0 < g < l) подключены к выходам k-х ячеек регистра сдвига, где k = m[(f - g)mod l] + g, выходы сумматоров первого блока подключены к первым входам блока сравнения, выходы сумматоров второго блока подключены к первым входам согласующего блока и вторым входам блока сравнения, выход которого подключен к второму входу согласующего блока, третий и четвертый входы которого объединены соответственно с третьим входом блока сравнения и тактовым входом регистра сдвига и являются входом записи и тактовым входом декодера, выход согласующего блока подключен к первому входу сумматора по модулю два, выход которого является выходом декодера, выход регистра сдвига подключен к второму входу сумматора по модулю два и первому информационному входу ключа, второй информационный и управляющий входы и выход которого подключены соответственно к информационному входу и входу синхронизации декодера и входу записи регистра сдвига.