Декодирование линейных кодов.

⇐ ПредыдущаяСтр 3 из 5Следующая ⇒

Пусть V – линейный -код, h – нулевой вектор и h₂, h_{3, …,} h_q^k– остальные кодовые векторы. Тогда таблица декодирования можно составить следующим образом. Кодовые векторы располагаются в виде строки с нулевым вектором слева. Затем один из наборов, не содержащийся в этой строке и имеющий разрядность n, например g_i помещается под вектором h. Далее строка заполняется так, чтобы под каждым кодовым вектором h_i помещался вектор . Аналогично в первый столбец очередной строки помещается вектор g₂ и строка заполняется таким же способом. Процесс продолжается до тех пор, пока каждый возможный набор длины n не появится где-нибудь в таблице. Данная таблица называется стандартным расположением и совпадает с таблицей смежных классов.

Теорема 3. Если стандартное расположение используется как таблица декодирования для блокового кода, то по полученному вектору u будет правильно декодирован переданный вектор v тогда и только тогда, когда набор ошибок является образующим смежного класса.

Доказательство: Если , где g_i – образующий i-го смежного класса, то вектор должен находиться в стандартом расположении в i-м смежном классе под кодовым словом u и поэтому будет правильно декодирован. Если же вектор не является образующим смежного класса, то вектор v должен находиться в некотором классе j с образующим g_j. Тогда вектор v расположен в j-й строке, но не под вектором u, потому что .

Пример:

*0000 *1011 *0101 *1110

1000 0011 1101 0110

0100 1111 0001 1010

0010 1001 0111 1100

а) 1011 ® 1001 ® 1001 (+) 0010 = 1011.

б) 0101 ® 0100 ® 0100 (+) 0100 = 0000 – неверно.

Другим важным случаем декодирования линейных кодов является синдромное декодирование.

Синдромное декодирование.

Предположим, что линейный код является нулевым пространством матрицы H размерности ( )*n. Для любого любого полученного на выходе вектора v вектор с компонентами называется синдромом. Поскольку рассматриваемый код – это нулевое пространство матрицы H, то некоторый вектор является словом тогда и только тогда, когда его синдром равен нулю.

Теорема 4. Два вектора v₁ и v₂ принадлежат одному и тому же смежному классу тогда и только тогда, когда их синдромы равны.

Доказательство: Два элемента группы v₁ и v₂ принадлежат одному и тому же смежному классу тогда и только тогда, когда есть элемент подгруппы, которой в данном случае является кодовое векторное пространство. Если кодовое пространство – это нулевое пространство матрицы H, то вектор принадлежит кодовому пространству тогда и только тогда, когда

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

Таким образом, вектор является кодовым вектором тогда и только тогда, когда синдромы векторов v₁ и v₂ равны.

Процесс декодирования может быть значительно упрощен за счет использования модифицированной таблицы декодирования. Таблица строится так, что в ней приводятся образующие смежных классов и синдромы для каждого из 2ⁿ^-^k смежных классов. После того как получен вектор, вычисляется его синдром. Затем то таблице отыскивается образующий смежного класса, являющийся предполагаемым набором ошибок и вычитается из полученного вектора. В результате образуется предположительно исходный кодовый вектор.

Пример:

(0000) 1011 0101 1110 (00)

(1000) 0011 1101 0110 (11)

(0100) 1111 0001 1010 (01)

(0010) 1001 0111 1100 (10)

0101®1101®1101 (+) 1000 = 0101

Синдромное декодирование позволяет сократить объем памяти при декодировании. Так, для кода (100, 80) необходимо в случае декодировании по лидеру смежного класса 2¹⁰⁰ входов, а в случае синдромного декодирования 2²⁰ входов.

Коды Хэмминга.

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

Пример:

Поскольку сумма любых двух столбцов этой матрицы не равна нулю и поскольку единственным отличным от нуля скаляром поля GF(2) является «1», то не существует ни одной нулевой линейной комбинации из двух столбцов матрицы H. Следовательно, нулевое пространство этой матрицы имеет минимальный вес равный 3, и является кодом, исправляющим все одиночные ошибки. Другие важные параметры кода Хэмминга:

- длина кодового вектора: 2^m-1;

- число проверочных символов: m;

- число информационных символов: /

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

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

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

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

Пример:

Декодирование такого кода осуществляется следующим образом:

Если синдром равен 0, то предполагается, что ошибок не было.
Если проверка по всем символам, соответствующая последней строке матрицы H дает «1» (проверка на четность), то предполагается, что произошла одна ошибка и слово можно исправить.

Если проверка на четность дает «0», а хотя бы один из остальных проверочных символов равен «1», то обнаружена неисправимая ошибка.

Коды Рида-Маллера.

Достоинства: можно получить большое Хэммингово расстояние и легко поддаются декодированию.

Для любых m и r< m существует код Рида-Маллера, для которого:

– разрядность кодового вектора,

– число информационных бит,

– число проверочных бит,

– минимальный вес кодового слова.

Рассмотрим следующую совокупность векторов над полем из двух элементов (0 и 1).

Пусть V₀ – вектор длины 2^m, все компоненты которого равны 1, V₁, V₂, …, V_m – строки матрицы, столбцами которой являются все возможные двоичные наборы длины m. Определим следующим образом векторное произведение двух векторов:

Рассмотрим совокупность векторов, образованную произведениями векторов v_i, взятых по два, три, четыре и т.д. вплоть до m.

v₀ = ( 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 )

v₄ = ( 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 )

v₃ = ( 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 )

v₂ = ( 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 )

v₁ = ( 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 )

v₄v₃ = ( 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 )

v₄v₂ = ( 0 0 0 0 0 0 0 0 0 0 1 1 0 0 1 1 )

v₄v₁ = ( 0 0 0 0 0 0 0 0 0 1 0 1 0 1 0 1 )

v₃v₂ = ( 0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 1 )

v₃v₁ = ( 0 0 0 0 0 1 0 1 0 0 0 0 0 1 0 1 )

v₂v₁ = ( 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 )

v₄v₃v₂= …

v₄v₃v₁= …

v₄v₂v₁= …

v₃v₂v₁= …

v₄v₃v₂v₁= …

Код Рида-Маллера порядка r определяется как код, базисом которого являются вектор v₀, v₁, …, v_m и все векторные произведения из r или меньшего числа этих векторов. Очевидно, что скалярное произведение двух векторов равно 0, если число единиц в векторном произведении четно и равно 1, если оно нечетно.

Для любого вектора v v²=v. Единственным произведением, содержащим нечетное число единиц, является произведение всех векторов v₁, …, v_m. Векторное произведение любого вектора из базиса кода порядка r на любой вектор из базиса кода порядка m-r-1 является вектором из базиса кода порядка m-1 и в нем содержится четное число единиц. Таким образом, любой вектор, принадлежащий коду порядка r, ортогонален любому базисному вектору, являющемуся произведением m-r-1 или меньшего числа векторов v₁, …, v_m. Из этого также следует, что код Рида-Маллера порядка r является нулевым пространством матрицы, образованной векторами v₀, v₁, …, v_m и всеми векторными произведениями этих векторов в количестве не более чем m-r-1, взятыми в качестве ее строк.

Важнейшая особенность кодов Рида-Маллера состоит в том, что декодирование для них может быть проведено достаточно простым способом.

Пример:

m=4, r=2, (16, 11)

Информационные символы этого кода кодируются следующим вектором:

Задача состоит в том, чтобы определить значения a по полученному вектору, несмотря на возможные ошибки. Очевидно, что сумма первых четырех компонент как элементов поля из двух элементов (0 и 1) равна нулю для всех базисных векторов, за исключением v₂v₁. Таким образом, если ошибок не было, то:

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

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

так, что следующая совокупность коэффициентов может быть определена аналогичным путём:

Идентичные уравнения можно записать для a₂, a₃, a₄. Если предположить, что ошибок не было, то

Этот вектор должен быть нулевым, если a₀=0 и единичным, если a₀=1, поэтому a₀ нужно выбирать равным тому из этих элементов, который появляется в векторе чаще.

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

Схему для определения того, суммы каких именно символов полученного вектора должны быть равны заданному информационному символу, можно описать следующим образом. Расположим символы в каждом из первоначальных векторов v₁, …, v_m, и назовем компоненту, соответствующую j-ому нулю в векторе v_i, и компоненту, соответствующую j-ой единице в векторе v_i, парными компонентами вектора v_i. Тогда 2⁽^m^-1) сумм парных компонент v_i используются для определения a_i. Далее, каждая из 2⁽^m^-2) сумм четырех компонент, используемых для определения a_ij, образуется некоторыми двумя парными компонентами вектора v_i и парными для этих уже выбранных компонент компонентами вектора v_j. Аналогично каждое соотношение, определяющее a_ijk, представляет собой сумму некоторых парных компонент вектора v_i плюс сумму компонент вектора v_j, парных к этим компонентам, и сумму компонент вектора v_k, парных к уже выбранным компонентам, так, что в каждой сумме получается всего 8 слагаемых. Этот процесс можно продолжить аналогичным образом.

Пример:

a₃:

v₃=(0000111100001111)

a₃=(b₁+b₅)=(b₂+b₆)=(b₃+b₇)=(b₄+b₈)=(b₉+b₁₃)=(b₁₀+b₁₄)=(b₁₁+b₁₅)=(b₁₂+b₁₆).

v₃=(0000111100001111)

v₁=(0101010101010101)

⇐ Предыдущая 1 234 5 Следующая ⇒