Методы кодирования LDPC кодов.
Кодирование – это операция выбора соответствующего кодового слова из множества всех кодовых слов с учетом вектора передаваемых информационных бит. В общем, кодирование может быть достаточно сложным из-за случайной структуры кода. Опишем некоторые методы кодирования, которые могут быть применены при кодировании любого LDPC кода.
Кодирование при помощи умножения матриц
В некоторых случаях применения двоичных кодов желательно, чтобы информационные биты явно содержались в соответствующем кодовом слове. Это позволит, например, избежать сложного декодирования, если система связи организована по очень хорошему каналу связи, вносящему малую неопределенность в принимаемую последовательность. Коды, выполняющие это условие называются систематическими. Часть кодового слова, повторяющая биты данных известна как систематическая часть кодового слова. В сверточном кодировании систематическая часть часто перемежается с несистематической (биты проверки). В этой главе мы рассмотрим систематические LDPC коды, систематическая часть которых состоит из первых бит в кодовом слове.
Так как коды ldpc являются линейными кодами, они могут кодироваться при помощи соответствующей N ×K порождающей матрицы G. В частности, кодовое слово может быть получено следующим образом
x = Ga,
- где а – вектор К информационных бит.
Так как код систематический, генерирующая матрица имеет вид:
(4.6)
- где P это (N−K)×K - матрица, которая формирует проверочные биты кодового слова.
Закодированный вектор х имеет форму
(a1, . . . , aK, p1, . . . , pN−K)T (4.7)
- где вектор проверочных бит p = (p1, . . . , pN−K)T = Pa .
Матрица определяется как
(3.8)
- это проверочная матрица систематического кода, полученного из порождающей матрицы G, означает, что вектор х является кодовым вектором если, и только если, выполняется соотношение:
(4.9)
Это может быть легко показано, так как любой вектор бит x = (x1, . . . , xN) является кодовым словом если последние (N – K) биты равны проверочным битам вектора р, сгенерированным по первым К битам кодового слова:
p = P(x1, . . . ,xK)T (4.10) Легко увидеть, что
равна 0, используя логическую алгебру, если, и только если,
то есть если х – кодовое слово.
Пораждающая матрица G полностью определяется своей подматрицей P, которая, в свою очередь, может быть вычислена при помощи преобразования данной проверочной матрицы H, в ее форме, при помощи простых операций с рядами (замена ряда линейной комбинацией ряда с другими рядами) [7].
Учтем проверочную матрицу H, для того, чтобы гарантировать существование соответствующего систематического кода, правая (N-K) × (N-K) суб-матрица H должна быть не единственной. Однако, следует заметить, что если H имеет максимальный ранг, то существует множество N – K столбцов матрицы H, которые формирует невырожденная матрица. Таким образом, можно получить проверочную матрицу соответствующего систематического кода, применяя перестановки столбцов H, которая ставит эти столбцы в правые позиции. Несмотря на это, H является редкой по определению, подматрицы Р от G, в общем, плотные. Это означает, что, отказываются от части единичной матрицы, для того, чтобы хранить G, по крайней мере,
бит памяти не требуется. С типичным LDPC кодами размер кодового слова колеблется от 103 до 104 бит, это означает, что память для хранения G, например, для кода скоростью 1/2, составляет по крайней мере порядка 106 бит.
Операция умножения матриц, выполняемая только для плотной части матрицы G, требует K(N-K)= К2(1/R-1) операций умножения и (К-1)(N-K)=(К2 -К)(1/R-1) дополнительных операций (логические операции).
|