Главная страница  |  Описание сайта  |  Контакты
СИСТЕМА ДЛЯ КОДИРОВАНИЯ И ДЕКОДИРОВАНИЯ С ИСПРАВЛЕНИЕМ ОШИБОК
СИСТЕМА ДЛЯ КОДИРОВАНИЯ И ДЕКОДИРОВАНИЯ С ИСПРАВЛЕНИЕМ ОШИБОК

СИСТЕМА ДЛЯ КОДИРОВАНИЯ И ДЕКОДИРОВАНИЯ С ИСПРАВЛЕНИЕМ ОШИБОК

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

1. С помощью поисковых систем

   С помощью Google:    

2. Экспресс-поиск по номеру патента


введите номер патента (7 цифр)

3. По номеру патента и году публикации

2000000 ... 2099999   (1994-1997 гг.)

2100000 ... 2199999   (1997-2003 гг.)
Номер патента: 2007042
Класс(ы) патента: H03M13/02
Номер заявки: 4913274/24
Дата подачи заявки: 22.02.1991
Дата публикации: 30.01.1994
Заявитель(и): Институт океанологии им.П.П.Ширшова РАН
Автор(ы): Морозов А.К.; Степин В.А.
Патентообладатель(и): Морозов Андрей Константинович; Степин Виктор Алексеевич
Описание изобретения: Изобретение относится к помехоустойчивому кодированию для защиты передаваемой по каналу информации от сбоев и ошибок, вызванных помехами.
Известно достаточно большое число помехоустойчивых кодов, исправляющих ошибки. Наиболее мощными современными системами кодирования и декодирования, исправляющими ошибки, являются системы с каскадными кодами. Для исправления t ошибок при правильном выборе кодов первой и второй ступеней каскадный код требует 2t проверочных символов. К недостаткам каскадного кода следует отнести неоднородность и логическую сложность его структуры и большое число многозначных логических элементов в кодере и декодере, обеспечивающих операции в конечном поле Галуа GF(q).
Цель изобретения - увеличение аппаратной надежности и быстродействия системы, вызванных сокращением числа ее логических элементов.
Цель достигается следующим способом. Информационные двоичные символы записываются в оперативное запоминающее устройство кодера группами по l - 1 двоичных символов по m - 1 строчкам матрицы размером (m - 1) x (l - 1), где l - простое число, l > m. Матрица дополняется проверками на четность по строкам и по столбцам и превращается в матрицу размером m x l. Символы из такой матрицы считываются по диагонали группами по m символов. Считывание начинается с элемента aoo, затем номер строки и номер столбца одновременно увеличиваются на единицу, пока не достигается элемент из последней строчки. Группа элементов aoo, а11, а22, . . . , am-1m-1 образует косой ряд. Далее считывание начинается с элемента а01 по такому же правилу, образуя косой ряд a01, a12, . . . , am-1m. По достижении последнего столбца его номер берется по модулю l и косой ряд продолжается с нулевого столбца. Порядковый номер считываемого символа n взаимно однозначно связан с номером строки i и номером столбца j соотношением
n = m[(j - 1) mod l] + i, где ( ) mod l - операция вычисления положительного остатка от деления на l. Каждой из этих групп сопоставляется один из 2m сигналов в канале связи. Декодер принимает информацию группами по m двоичных символов и восстанавливает исходную матрицу из принятых символов. Далее он вычисляет двоичные суммы символов по строкам и по столбцам, образуя векторы из m проверок по строкам и первых m проверок по столбцам. Производится циклический сдвиг принятых символов поблочно по m двоичных символов до тех пор, пока группа из m первых проверок по столбцам не совпадает с вектором проверок по строкам. В случае совпадения эта группа складывается покомпонентно по модулю два с первым блоком из m двоичных символов и ошибки исправляются.
Рассмотрим матрицу информационных символов aij размером (m - 1) x (l - 1) и дополним ее проверочными символами на четность bij как по строкам, так и по столбцам. Результирующая матрица показана на фиг. 2.1; на фиг. 2.2 показан порядок считывания матрицы при m = 4, l = 5; на фиг. 2,3а приводится матрица, в которой произошли ошибки во втором косом ряду. Изначально матрица содержала только нулевые элементы. Векторы проверочных сумм по столбцам и по строкам не совпадают. После циклического сдвига на одну группу из четырех двоичных символов ошибочный косой ряд попадает на первое место и векторы проверок по строкам и по столбцам совпадают (см. фиг. 2,3б). Если добавить проверочные символы по модулю два к первому косому ряду, ошибки исправятся. Матрица снова станет нулевой. Такой способ кодирования и коррекции ошибок проще известного ранее, что служит достижению цели. Устройство, реализующее данный способ кодирования, состоит из кодера и декодера, схемы которых приведены на фиг. 4, 5 и 6.
Кодер (фиг. 4) состоит из регистра 9 сдвига, в который информация записывается в порядке, указанном в способе, и сумматоров 1-8 по модулю два.
Кодер для кода длиной l символов из алфавита размером 2m состоит из регистра 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 символов поступают в модулятор, где им сопоставляются сигналы из ансамбля с 2m членами. Эти сигналы передаются по каналу связи.
На фиг. 4 приводится принципиальная схема кодера для кода длиной 5 символов из алфавита 24.
Общая схема декодера приводится на фиг. 2.5. Декодер состоит из регистра 10 сдвига, в котором информация хранится в порядке, описанном выше, первого 11 и второго 12 блоков сумматоров (логических цепей, вычисляющих проверочные суммы (синдромы) по столбцам 11 и по строкам 12), блока 13 сравнения, согласующего блока 14, сумматора 15 по модулю два (схемы покомпонентного суммирования по модулю два) и ключа. При этом группа из m двоичных символов, расположенных в косом ряду, начиная с элемента в первой строке, рассматривается как многозначный символ из алфавита 2m. В регистре сдвига эта группа символов располагается в соседних ячейках.
Для кода длиной l символов из алфавита 2m регистр 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. С-выход этого триггера управляется сигналами символьной синхронизации Т1, которые следуют каждые m тактов То. Выход D-триггера - выход блока сравнения.
Согласующий блок 14 состоит из регистра 31 последовательного сдвига из m ячеек, логического элемента И 32. Входы ячеек регистра сдвига подключены к выходам соответствующих сумматоров логической схемы, вычисляющей проверочные суммы по строкам (или по столбцам). Выход регистра сдвига подключен к первому входу логического элемента И 32. Второй вход этого элемента подключен к выходу D-триггера 30 блока сравнения. Запись в регистр сдвига производится сигналами Т1, а тактирование - сигналами То. Выход логического элемента И 32 подключен к двухвходовому сумматору 33 по модулю два. Этот сумматор реализует покомпонентное суммирование. Выход сумматора представляет собой выход всей схемы, а второй его вход подключен в соответствии с общей схемой к выходу регистра 16 последовательного сдвига. Выход регистра через ключ 34 подключен к его входу. Ключ управляется сигналом синхронизации по кодовым группам Т2 (на общей схеме ключ не выделен).
Декодер работает следующим образом.
Приходящая кодовая комбинация через ключ 34 поступает на вход регистра 16 последовательного сдвига и записывается в него группами по m двоичных символов (косой ряд), рассматриваемых как многозначный символ из алфавита 2m.
На выходе двоичных сумматоров 17-24 логических цепей, вычисляющих проверочные символы как по строкам, так и по столбцам, образуются потенциалы, соответствующие проверочным символам. Проверки на четность по строкам образуют вектор S1 из m элементов. Проверки по столбцам образуют вектор S2 из m элементов. Проверки на четность в последних столбцах не производятся. Если ошибка содержится в первой группе из m двоичных элементов, расположенных в косом ряду, начиная с первого элемента матрицы, то вектор проверок по столбцам совпадает с вектором проверки по строчкам. Добавляя покомпонентно по модулю два вектор S1 к первой группе из m двоичных символов, ошибку можно исправить. Этот случай соответствует ошибке в первом многозначном символе из алфавита 2m. Если ошибка произошла в другом многозначном символе (в другой группе из m двоичных символов, расположенных в косом ряду, начиная с элемента в первой строке), то декодер начинает сдвигать в цикле информацию, записанную в регистре, группами по m двоичных чисел (т. е. равно по одному многозначному символу) и сравнивать проверочные векторы S1 и S2. Если S1 = S2, значит ошибочная группа из m двоичных символов оказалась на первом месте и ее можно исправлять, складывая ее покомпонентно по модулю два с проверочным вектором S1 = S2. При циклическом сдвиге информации в регистре группами по m двоичных знаков косые ряды сдвигаются по матрице по кругу. При этом вектор проверок по столбцам сохраняется, а вектор проверок по строкам циклически сдвигается. Если число столбцов простое, то среди l последовательных циклических сдвигов нет ни одной одинаковой пары. Все l сдвигов, соответствующих расположению на первом месте l различных последовательных многозначных символов, различны. Следовательно, такой метод декодирования однозначен.
Такой код исправляет однократный сбой в группе из m двоичных символов или одну ошибку в многозначном символе из алфавита 2m. Число проверочных символов: две группы по m двоичных знака или два символа из алфавита 2m. Таким образом, данный способ кодирования на исправление одного многозначного символа тратит два проверочных символа из того же многозначного алфавита. Рассмотренный код эквивалентен лучшим из известных кодов, исправляющих один многозначный символ: многозначному коду Хэмминга с двумя проверочными символами или коду Рида-Соломона также с двумя проверочными символами. По сравнению с этими известными кодами рассмотренный способ кодирования выгодно отличается более простым декодером.
Рассмотренная схема не содержит сложных логических элементов, реализующих умножение и сложение в поле Галуа из 16 элементов. Вместо сложных логических схем умножения и сложения в целочисленном поле Галуа используются схемы ИСКЛЮЧАЮЩЕЕ ИЛИ, два регистра, D-триггер, элемент ИЛИ-НЕ, реализованные в виде стандартных микросхем. Простота реализации и структуры декодера выгодно отличает его от известных аналогов и прототипов. Более простые схемы кодера и декодера позволяют повысить надежность кодера и увеличить быстродействие кодирования и декодирования информации. Предлагаемая система исправляет не только однократные двоичные ошибки, но и сбои целых групп по m двоичных символов, что повышает надежность работы кодера в канале с шумом при передаче информации с помощью многозначных сигналов. (56) Авторское свидетельство СССР N 1109924, кл. H 04 L 1/10, 1983.
Авторское свидетельство СССР N 1358098, кл. H 03 M 13/00, 1985.
Формула изобретения: СИСТЕМА ДЛЯ КОДИРОВАНИЯ И ДЕКОДИРОВАНИЯ С ИСПРАВЛЕНИЕМ ОШИБОК состоящая из кодера, выполненного на регистре сдвига, и декодера, содержащего первый и второй блоки сумматоров и сумматор по модулю два, выход которого является выходом декодера, отличающаяся тем, что, с целью повышения надежности системы и ее быстродействия, в кодер введены l сумматоров по модулю два с m - 1 входами (где l - простое число; m - длина многозначного кода с символами из алфавита 2m), 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, выходы сумматоров первого блока подключены к первым входам блока сравнения, выходы сумматоров второго блока подключены к первым входам согласующего блока и вторым входам блока сравнения, выход которого подключен к второму входу согласующего блока, третий и четвертый входы которого объединены соответственно с третьим входом блока сравнения и тактовым входом регистра сдвига и являются входом записи и тактовым входом декодера, выход согласующего блока подключен к первому входу сумматора по модулю два, выход которого является выходом декодера, выход регистра сдвига подключен к второму входу сумматора по модулю два и первому информационному входу ключа, второй информационный и управляющий входы и выход которого подключены соответственно к информационному входу и входу синхронизации декодера и входу записи регистра сдвига.