СПОСОБ МЯГКОГО ДЕКОДИРОВАНИЯ СИСТЕМАТИЧЕСКИХ БЛОКОВЫХ КОДОВ Российский патент 2012 года по МПК H03M13/05 H03M13/45 H04L1/20 

Описание патента на изобретение RU2444127C1

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

Заявленное техническое решение расширяет арсенал применения помехоустойчивых систематических блоковых кодов.

Известны способы декодирования блоковых кодов (см. Дж.Кларк, мл., Дж Кейн. «Кодирование с исправлением ошибок в системах цифровой связи». М.: Радио и связь, 1987, с.96-128), в которых комбинации ошибок отыскиваются путем, отличным от процедуры умножения принятого кодового вектора на проверочную матрицу и получивших наименование неалгебраических алгоритмов.

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

Известен также способ декодирования блоковых кодов со стираниями элементов (см. патент РФ 2327297), в котором пространство кодовых комбинаций разбивается на кластеры и при правильном определении номера кластера декодирование осуществляется в подмножестве комбинаций, принадлежащих выделенному кластеру с использованием метрики Евклида.

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

Наиболее близким по технической сущности к заявленному является способ мягкого декодирования систематических блоковых кодов с использованием упорядоченных статистик (см. Р.Морелос-Сарагоса. Искусство помехоустойчивого кодирования. Методы, алгоритмы, применение. М.: Техносфера, 2005, с.213, …, 216), в соответствии с которым мягкое декодирование блоковых кодов заключается в том, что символы принятой кодовой комбинации V систематического (n,k)-кода по основному алгоритму упорядочиваются по убыванию их градаций надежности и на основании выполненных перестановок формируется вектор V′, который совместно с вектором V образует двудольный граф для формирования матрицы перестановок Р, умножение на которую порождающей матрицы кода G приводит к получению новой матрицы G′, первые k столбцов которой проверяются на предмет линейной независимости и в случае положительного результата этой проверки матрица G′ приводится к систематической форме , при этом первые k наиболее надежных элементов вектора V′ путем умножения на образуют вектор эквивалентного кода Vэкв, который при поэлементном сложении по модулю два с вектором V′ формирует переставленный вектор ошибок Е′ и после умножения вектора Е′ на РT формируется вектор ошибок Е, действовавший в канале связи на вектор V, при этом в случае отрицательного результата проверки линейной независимости строк матрицы G′ осуществляется замена k-того столбца этой матрицы на (k+1)-й столбец и в случае необходимости на последующие столбцы до выполнения условия линейной независимости k первых столбцов матрицы G′ и при выполнении этого условия адекватно меняются местами элементы в векторе V′ и столбцы в матрице Р.

Достоинством данного способа декодирования является возможность исправлять число ошибок, кратность которых превосходит число ошибок, определяемых метрикой Хэмминга.

Недостаток прототипа заключается в низкой скорости декодирования из-за необходимости вычисления детерминантов матриц размерности k×k при оценке свойств нелинейности строк переставленной матрицы G′. С ростом значения k (на практике используют коды с большим значением этого параметра) число элементарных операций при вычислении детерминанта имеет экспоненциальную зависимость. Поэтому даже незначительное сокращение размерности матрицы, по которой определяют выполнение свойства линейной независимости матрицы G′, обеспечивает выигрыш скорости декодирования.

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

Поставленная цель достигается тем, что символы принятой кодовой комбинации V систематического (n,k)-кода по основному алгоритму упорядочиваются по убыванию их градаций надежности и на основании выполненных перестановок формируется вектор V′, который совместно с вектором V образуют двудольный граф для формирования матрицы перестановок Р, умножение на которую порождающей матрицы кода G приводит к получению новой матрицы G′, первые k столбцов которой проверяются на предмет линейной независимости и в случае положительного исхода этой проверки матрица G′ приводится к систематической форме , при этом первые k наиболее надежных элементов вектора V путем умножения на образуют вектор эквивалентного кода Vэкв, который при поэлементном сложении по модулю два с вектором V′ формирует переставленный вектор ошибок Е′ и после умножения вектора Е′ на РT формируется вектор ошибок Е, действовавший в канале связи на вектор V, при этом в случае отрицательного результата проверки линейной независимости строк матрицы G′ осуществляется замена k-го столбца этой матрицы на (k+1)-й столбец и в случае необходимости на последующие столбцы до выполнения условия линейной независимости k первых столбцов матрицы G′ и при выполнении этого условия адекватно меняются местами элементы в V′ и столбцы Р, отличающийся тем, что для всех разрешенных кодовых комбинаций (n,k)-кода по их f старшим разрядам определяют номер кластера, при этом значение f выбирают в пределах 1<ƒ≤k/2, и при формировании кодового вектора на передаче младший разряд комбинации (правый) выкалывается и заменяется на бит проверки четности f разрядов кластера, а приемник, приняв вектор V, по градациям надежности и биту четности оценивает правильность приема номера кластера и в случае положительного решения переходит к обработке (n-ƒ, k-ƒ)-кода по основному алгоритму, предварительно сформировав корректирующий вектор Wук путем умножения разрядов номера кластера на первые f строк порождающей матрицы G кода и последующего временного удаления из него разрядов кластера, после чего вектор Wук вычитается из вектора V, при этом разряды кластера вектора V также не учитываются, с присвоением младшему разряду вновь образованного вектора Vук наиболее низкой оценки градации надежности, после чего декодер работает по основному алгоритму, формируя векторы ошибок Е, который поразрядно складывается с векторами Wук, Vук, формируя переданный вектор V за счет возвращения на свои места старших разрядов номера кластера, при этом, если проверка на четность номера кластера не выполняется, декодер подвергает инверсии наиболее ненадежный бит из числа участвующих в проверке.

Проведенный анализ уровня техники позволил установить, что аналоги, характеризующиеся совокупностью признаков, тождественных всем признакам заявленного технического решения, отсутствуют, что указывает на соответствие заявленного способа условию патентоспособности «новизна». Результаты поиска известных решений в данной и смежной областях техники с целью выявления признаков, совпадающих с отличными от прототипа признаками заявленного объекта, показали, что они не следуют явным образом из уровня техники. Из уровня техники также не выявлена известность влияния предусматриваемых существенными признаками заявленного изобретения преобразований на достижение указанного технического результата. Следовательно, заявленное изобретение соответствует условию патентоспособности «изобретательский уровень».

Иллюстрация способа осуществляется на примере кода БЧХ (15,7,5) и применима к любому систематическому блоковому коду.

Поставленная цель достигается следующим образом. Код с порождающим полиномом g(x)=7218 и ƒ=3 имеет порождающую матрицу G в систематической форме вида:

Пусть на выходе кодера образовался вектор вида

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

Приемник принимает вектор, устанавливая по какому-либо известному принципу градацию надежности для каждого символа. Пусть соответствие символов и градаций надежности символов (далее оценки) имеет вид

следовательно, вектор ошибок представлен последовательностью

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

Номер восстановленного кластера имеет значение 410. Декодер переходит на укороченный код (12,4,5), порождающая матрица которого имеет вид

Далее формируется корректирующий вектор W путем умножения номера кластера на первые три строки порождающей матрицы G. Тогда

и после исключения из него разрядов кластера вектор имеет вид

Складывая по модулю два с соответствующими разрядами принятого вектора V и Wук, получаем вектор укороченного кода Vук.

Младшему разряду этого вектора искусственно присваивается наиболее низкий индекс достоверности символа (в нашем случае 0, показан курсивом). После чего выполняется основной алгоритм декодера, представленный ниже:

Порядковая нумерация 1 2 3 4 5 6 7 8 9 10 11 12 Vук 0 0 1 1 1 1 1 0 0 0 0 1 Оценки 7 1 1 1 7 7 7 7 7 5 5 0 Новая нумерация символов 1 5 6 7 8 9 10 11 2 3 4 12 Значения переставленных символов Vпром 0 1 1 1 0 0 0 0 0 1 1 1

В этом алгоритме переходы от элементов строки «Порядковая нумерация» к элементам строки «Новая нумерация символов» представляются двудольным графом, на основании которого по общеизвестным правилам формируется матрица перестановок Р размерности (n-ƒ)×(n-ƒ). Путем умножения матрицы Р на матрицу Gук получают результат предварительного преобразования, который необходимо оценить с точки зрения сохранения свойства нелинейности строк новой матрицы G′.

Для этого из G′ выделяются первые k-ƒ=λстолбцов с образованием матрицы Аλ×λ, для которой проверяют условие det Aλ×λ≠0 и выполняется действие по вычислению обратной матрицы , структура которой точно указывает на порядок комбинирования строк матрицы G′ для получения в систематической форме порождающей матрицы . Например, для G′ имеем

Если условие det Аλ×λ≠0 не выполняется, то 4-й столбец матрицы G′ меняется местами с 5-м столбцом. Если и в этих условиях детерминант оказывается равным нулю, то 4-й столбец матрицы G′ меняется местами с 6-м столбцом. После вычисления вычисляется порождающая матрица эквивалентного кода в систематической форме

Вектор 0111, выделенный в таблице, умножается на новую порождающую матрицу, в результате образуется вектор

Вектор Vэкв поразрядно сравнивается со значениями вектора Vпром.

Комбинация эквивалентного кода Vэкв 0 1 1 1 0 0 1 1 1 0 0 0 Значения переставленных символов Vпром 0 1 1 1 0 0 0 0 0 1 1 1 Условный вектор ошибок eуcлв 0 0 0 0 0 0 1 1 1 1 1 1

Выполнив операцию eуслв×PT=e, декодер получает вектор ошибок, действовавший в канале связи при передаче кодового вектора. Для получения истинного вектора укороченного кода необходимо сложить по модулю 2 три вектора: вектор ошибок е, корректирующий вектор Wук и вектор укороченного кода Vук.

Комбинация укороченного кода Vук 0 0 1 1 1 1 1 0 0 0 0 1 Wук 0 0 0 0 1 1 1 0 1 0 0 0 Вектор ошибок е 0 1 1 1 0 0 0 0 0 1 1 0 Результат сложения 0 1 0 0 0 0 0 0 1 1 1 1

К результату сложения справа необходимо добавить три старших разряда, отвечающих за номер кластера.

Комбинация укороченного
кода Vук
Позиции разрядов кластера 0 1 0 0 0 0 0 0 1 1 1 1
Комбинация с номером кластера 1 0 0 0 1 0 0 0 0 0 0 1 1 1 1 Вектор, принятый из канала связи 1 0 0 0 1 0 0 0 0 0 0 1 1 1 1

Применение предложенного способа мягкого декодирования систематических блоковых позволяет сократить время обработки кодовых комбинаций в декодере за счет снижения размерности вычисляемых матриц. Например, вычисление детерминанта матрицы размерности 4×4 потребует выполнения 59 элементарных операций, а аналогичные вычисления, проведенные для матрицы размерности 7×7 потребуют выполнения 12599 подобных операций (снижение вычислительных затрат в 213 раз). Кроме того, способ обеспечивает защиту кластера без введения дополнительной избыточности, а также исправление стираний за пределами тех возможностей, которые определяются метрикой Хэмминга.

Похожие патенты RU2444127C1

название год авторы номер документа
СПОСОБ МЯГКОГО ДЕКОДИРОВАНИЯ БЛОКОВЫХ КОДОВ 2015
  • Гладких Анатолий Афанасьевич
RU2580797C1
ДЕКОДЕР С УПОРЯДОЧЕННОЙ СТАТИСТИКОЙ СИМВОЛОВ 2012
  • Гладких Анатолий Афанасьевич
  • Капустин Дмитрий Александрович
  • Логинова Ксения Евгеньевна
  • Ермолаева Анна Сергеевна
RU2490804C1
Перестановочный декодер с режимом обучения 2017
  • Гладких Анатолий Афанасьевич
  • Маслов Александр Алексеевич
  • Пчелин Никита Александрович
  • Тамразян Георгий Михайлович
  • Баскакова Екатерина Сергеевна
RU2644507C1
СПОСОБ МЯГКОГО КОГНИТИВНОГО ДЕКОДИРОВАНИЯ СИСТЕМАТИЧЕСКИХ БЛОКОВЫХ КОДОВ 2016
  • Гладких Анатолий Афанасьевич
  • Ганин Дмитрий Владимирович
  • Сорокин Иван Александрович
  • Шамин Алексей Анатольевич
  • Чилихин Николай Юрьевич
RU2646372C1
ПЕРЕСТАНОВОЧНЫЙ ДЕКОДЕР С СИСТЕМОЙ БЫСТРЫХ МАТРИЧНЫХ ПРЕОБРАЗОВАНИЙ 2019
  • Пчелин Никита Александрович
  • Гладких Анатолий Афанасьевич
  • Климов Даниил Витальевич
RU2718224C1
Способ перестановочного декодирования блоковых кодов на базе упорядоченной когнитивной карты 2018
  • Гладких Анатолий Афанасьевич
RU2697732C1
ПЕРЕСТАНОВОЧНЫЙ ДЕКОДЕР С ПАМЯТЬЮ 2017
  • Гладких Анатолий Афанасьевич
  • Ганин Дмитрий Владимирович
  • Сорокин Иван Александрович
  • Шамин Алексей Анатольевич
  • Шахтанов Сергей Валентинович
RU2672300C2
СПОСОБ ДИНАМИЧЕСКОГО УПРАВЛЕНИЯ ПРОПУСКНОЙ СПОСОБНОСТЬЮ КАНАЛА СВЯЗИ НА БАЗЕ КЛАСТЕРНОГО ДЕКОДИРОВАНИЯ ПОЛЯРНЫХ КОДОВ 2021
  • Чилихин Николай Юрьевич
RU2779158C1
ПЕРЕСТАНОВОЧНЫЙ ДЕКОДЕР С ОБРАТНОЙ СВЯЗЬЮ 2018
  • Сорокин Иван Александрович
  • Шамин Алексей Анатольевич
  • Шахтанов Сергей Валентинович
RU2704722C2
ДЕКОДЕР С ИСПРАВЛЕНИЕМ СТИРАНИЙ 2008
  • Агеев Сергей Александрович
  • Гладких Анатолий Афанасьевич
  • Кержнер Дмитрий Алексеевич
  • Кулешов Игорь Александрович
  • Петров Валерий Владимирович
  • Репин Геннадий Александрович
  • Служивый Максим Николаевич
RU2379841C1

Реферат патента 2012 года СПОСОБ МЯГКОГО ДЕКОДИРОВАНИЯ СИСТЕМАТИЧЕСКИХ БЛОКОВЫХ КОДОВ

Изобретение относится к технике связи и может использоваться в системах передачи дискретной информации. Техническим результатом является повышение скорости декодирования и достоверности принимаемой информации. Это достигается тем, что для всех разрешенных кодовых комбинаций систематического (n,k)-кода по их f старшим разрядам определяют номер кластера, при этом значение f выбирают в пределах 1<ƒ≤k/2. Принимают вектор V и по градациям надежности и биту четности оценивают правильность приема номера кластера. В случае положительного решения переходят к обработке (n-ƒ, k-ƒ)-кода с использованием упорядоченной статистики, предварительно сформировав корректирующий вектор Wук путем умножения f разрядов на первые f строк порождающей матрицы G кода и временного удаления из него разрядов кластера, после чего вектор Wук вычитается из вектора V, у которого также не учитываются разряды кластера, с присвоением младшему разряду вновь образованного вектора Vyr наиболее низкой оценки градации надежности. Оставшиеся символы упорядочиваются по убыванию их оценок. Вектор ошибок Е для укороченного кода отыскивается с использованием эквивалентного кода и после его вычисления декодер осуществляет поразрядное сложение векторов Wук, Vук и Е, формируя переданный вектор за счет возвращения на места старших разрядов номера кластера, при этом, если проверка на четность номера кластера не выполняется, декодер подвергает инверсии самый ненадежный бит из числа проверяемых. 4 табл.

Формула изобретения RU 2 444 127 C1

Способ мягкого декодирования систематических блоковых кодов, заключающийся в том, что символы принятой кодовой комбинации V систематического (n,k)-кода по основному алгоритму упорядочиваются по убыванию их градаций надежности и на основании выполненных перестановок формируется вектор V', который совместно с вектором V образуют двудольный граф для формирования матрицы перестановок Р, умножение на которую порождающей матрицы кода G приводит к получению новой матрицы G', первые k столбцов которой проверяются на предмет линейной независимости и в случае положительного исхода этой проверки матрица G' приводится к систематической форме G's, при этом первые k наиболее надежных элементов вектора V' путем умножения на G's образуют вектор эквивалентного кода Уэкв, который при поэлементном сложении по модулю два с вектором V' формирует переставленный вектор ошибок Е' и после умножения вектора Е' на Pт формируется вектор ошибок Е, действовавший в канале связи на вектор V, при этом в случае отрицательного результата проверки линейной независимости строк матрицы G' осуществляется замена k-го столбца этой матрицы на (k+1)-й столбец и в случае необходимости на последующие столбцы до выполнения условия линейной независимости k первых столбцов матрицы G' и при выполнении этого условия адекватно меняются местами элементы в V' и столбцы Р, отличающийся тем, что для всех разрешенных кодовых комбинаций (n,k)-кода по их f старшим разрядам определяют номер кластера, при этом значение f выбирают в пределах 1<ƒ≤k/2 и при формировании кодового вектора на передаче младший разряд комбинации (правый) выкалывается и заменяется на бит проверки четности f разрядов кластера, а приемник, приняв вектор V по градациям надежности и биту четности, оценивает правильность приема номера кластера и в случае положительного решения переходит к обработке (n-ƒ, k-ƒ)-кода по основному алгоритму, предварительно сформировав корректирующий вектор Wук путем умножения разрядов номера кластера на первые f строк порождающей матрицы G кода и последующего временного удаления из него разрядов кластера, после чего вектор Wук вычитается из вектора V, при этом разряды кластера вектора V также не учитываются, с присвоением младшему разряду вновь образованного вектора Vук наиболее низкой оценки градации надежности, после чего декодер работает по основному алгоритму, формируя вектора ошибок Е, который поразрядно складывается с векторами Wук, Vук, формируя переданный вектор V за счет возвращения на свои места старших разрядов номера кластера, при этом, если проверка на четность номера кластера не выполняется, декодер подвергает инверсии наиболее ненадежный бит из числа участвующих в проверке.

Документы, цитированные в отчете о поиске Патент 2012 года RU2444127C1

МОРЕЛОС-САРАГОСА Р
Искусство помехоустойчивого кодирования
Методы, алгоритмы, применение
- М.: Техносфера, 2005, с.213-216
US 2010169746 A1, 01.07.2010
Регулятор подвижности бетонной смеси 1986
  • Адаскин Михаил Григорьевич
  • Горенко Иван Георгиевич
  • Дороганич Сергей Корнеевич
  • Макеев Александр Юрьевич
  • Яковис Леонид Моисеевич
SU1333586A1
US 2009138780 A1, 28.05.2009
ВОЗДУШНЫЙ ДИФФУЗОР, ПРЕДНАЗНАЧЕННЫЙ ДЛЯ УСТАНОВКИ НА ВРАЩАЮЩЕМСЯ МОДУЛЕ СОПРЯЖЕНИЯ СИСТЕМЫ ОХЛАЖДЕНИЯ ОРИЕНТИРУЕМОГО ДВИЖИТЕЛЬНОГО УСТРОЙСТВА 2021
  • Мело Жульен
RU2814871C1
ДЕКОДЕР С ИСПРАВЛЕНИЕМ СТИРАНИЙ 2008
  • Агеев Сергей Александрович
  • Гладких Анатолий Афанасьевич
  • Кержнер Дмитрий Алексеевич
  • Кулешов Игорь Александрович
  • Петров Валерий Владимирович
  • Репин Геннадий Александрович
  • Служивый Максим Николаевич
RU2379841C1
ДЕКОДЕР С ИСПРАВЛЕНИЕМ СТИРАНИЙ 2007
  • Гладких Анатолий Афанасьевич
  • Черторийский Сергей Юрьевич
  • Тетерко Вадим Владимирович
  • Шакуров Радик Шамильевич
  • Закирова Лилия Рэстемовна
RU2344556C1

RU 2 444 127 C1

Авторы

Гладких Анатолий Афанасьевич

Даты

2012-02-27Публикация

2010-08-24Подача