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

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

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

Известны способы декодирования блоковых кодов (см. Дж.Кларк, мл., Дж Кейн. «Кодирование с исправлением ошибок в системах цифровой связи». М.: Радио и связь, 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)=721₈ и ƒ=3 имеет порождающую матрицу G в систематической форме вида:

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

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

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

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

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

Номер восстановленного кластера имеет значение 4₁₀. Декодер переходит на укороченный код (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_услв×P^T=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 раз). Кроме того, способ обеспечивает защиту кластера без введения дополнительной избыточности, а также исправление стираний за пределами тех возможностей, которые определяются метрикой Хэмминга.

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

Способ мягкого декодирования систематических блоковых кодов, заключающийся в том, что символы принятой кодовой комбинации 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 за счет возвращения на свои места старших разрядов номера кластера, при этом, если проверка на четность номера кластера не выполняется, декодер подвергает инверсии наиболее ненадежный бит из числа участвующих в проверке.