Быстрое декодирование кодов Голда

Пусть - матрица размера 2^2k× n, строками которой являются нулевая последовательность и все последовательности Голда; А - матрица, получен­ная из преобразованием 0→1 1→-1;M₁ и М₂ - последовательности максимальной длины с проверочными полиномами h₁(X) и h₂(X), выбран­ные для образования кода Голда. Обозначим К₁ и К₂ соответствующие коды максимальной длины. Каждый код состоит из нулевой последовательности и всех циклических перестановок последовательности максимальной длины. Ансамбль последовательности Голда является прямым произведением мно­жеств K₁ и К₂.

Упорядочим эти последовательности в матрице следующим образом. В строках с номерами 1, 2^k ∙ j +1,j=1,2,…,2^K-1, разместим слова кода К₁ в порядке возрастания информационной части (первые k символов), т.е. в пер­вой строке запишется слово из нулей A₀ в строке с номером 2^K+1 - слово A₁, первые k символов которого образуют число 1, а в строке с номером 2*2+1 - слово А₂, первые к символов которого образуют число 2, и т.д. Эти строки называют образующими. В остальных строках матрицы запишем суммы по модулю два элементов кода К₂ с соответствующей образующей строкой А_j. Построенная таким образом матрица имеет следующий вид:

Матрица представляет собой разложение кода Голда на смежные клас­сы по подкоду К₂.

Для реализации декодирования кодов Голда по методу максимального правдоподобия необходимо вычислить векторно-матричное произведение.

Для реализации декодирования кодов Голда по методу максимального правдоподобия необходимо вычислить векторно-матричное произведение (ВМП) кодовой матрицы и входного вектор-сигнала. Для декодирования ко­дов Голда применяют два алгоритма вычисления ВМП, которые различают­ся по способу факторизации кодовой матрицы.

Переставим столбцы матрицы при помощи подстановки и по­лучим матрицу Адамара. Известно, что для матриц Адамара справедливо ре­куррентное соотношение

Из чего следует, что матрицу А можно представить в виде:

где В₁ - матрица размера 2^2к-1х(2^k-1-1), а В₂ - матрица размером

2^2k-1х2^k-1. Эта процедура деления может быть продолжена рекурсивно с матрицами B₁ и В₂.

Разобьем вектор входного сигнала на две части X = (Х₁,Х₂)^T, где Х₁ имеет длину 2^k-1-1, a X₂ - длину 2^k-1. Тогда:

Y = А∙X = (В₁Х₁ + В₂Х₂,В₁Х₁ - В₂Х₂)^T.

Если известны произведения В₁Х₁, В₂Х₂, то для вычисления АХ гре- буется выполнить 2^k операций. Эти вычисления сводятся к умножению вектора Y_k-1 = (В₁Х₁,В₂Х₂)^T на матрицу:

С_к = Н₂⨂I₂⨂.... ⨂I₂,

где I₂ - единичная матрица порядка два, а знак ⨂обозначает прямое произ­ведение матриц. Для вычисления произведения В₁Х₁ и B₂X₂ можно снова воспользоваться структурными свойствами матриц В₁ и В₂, а именно:

Блок I₁ имеет размер 2^2k-2 х(2^к-2-1), а блоки l ₂, q₁,q₂ - размер

2^2k-2x2^k-2. Аналогично предыдущему выполнение этих операций эквива­лентно умножению на матрицу:

С_к-1 = I₂ ⨂Н₂ ⨂I₂ ⨂....⨂I₂.

Эта итеративная процедура закончится на i-м шаге, где i равно мини­мальному решению неравенства 2k-i≥2^k-i

Неравенство определяет размер блочных подматриц, на которые делит­ся матрица А.. Блоки первого столбца имеют размер 2^2к-iх(2^k-i -1), а ос­тальные блоки - размер 2^2k-iх2^k-i. Все они образуются первыми 2^2k-i стро­ками матрицы А. Число различных блоков равно 2ⁱ. Обозначим их γ₀,γ₁,…,γ₂^i-1. Характерной чертой матриц γ_j,j=1,..., 2ⁱ-1, является то, что

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

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

Умножение вектора на любую их матриц γ_j не сложнее, чем умноже­ние на матрицу полного кода. Поэтому количество операций для вычисле­ний не превышает 2^2ks(2^k-i), где s(2^k-i)≈0.5.

39. Код с проверкой на четность итеративные коды.

Код с проверкой на четность

1. Такой код образуется путем добавления к передаваемой комбинации, состоящей из к информационных символов неизбыточного кода, одного контрольного символа (0 или 1), так чтобы общее число единиц в передаваемой комбинации было четным. Таким образом, общее число символов n в передаваемой комбинации:

n=k+ 1 В первом столбце приведены примеры

k	m	n = k+m
		11011 0 11011 1 00010 1 11101 0 11111 1

передачи отдельных комбинаций пятиразрядного двоичного кода на все сочетания (k - символы).

Во втором столбце к этим комбинациям приписывается контрольный символ 1, если сумма единиц в кодовой комбинации нечетная, или 0, если сумма единиц четная. В нашем примере длина исходной кодовой комбинации k =5 позволяет при таком числе разрядов передать N =2⁵=32 кодовые комбинации. И хотя приписывание контрольного символа и увеличивает разрядность кода до n =6, число передаваемых комбинаций остается прежним. Поэтому общее число комбинаций.

N=2^n-1

Таким образом, этот код обладает избыточностью, т.к. в нашем примере вместо N =2⁶=64 комбинаций может быть послано только N =2^6-1=32 комбинаций.

В кодировании избыточности определяется отношением контрольных символов m к информационным k в одном слове:

(3-8)

Для пятиразрядного кода с проверкой на четность И=1/5. Очевидно, что чем длиннее кодовая комбинация, тем меньше избыточность и больше экономичность кода. Добавление контрольного символа увеличивает кодовое расстояние в передаваемых комбинациях от d =1 до d_min= 2.

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

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

По изложенному принципу строится код с проверкой на нечетность.

2 итеративные коды