Корректирующих однократные ошибки

В зависимости от требуемой разрядности кода записывается единичная матрица (n n)

С помощью этой матрицы можно записать все комбинации n-разрядного оптимального кода.

Чтобы образовать на основании этой матрицы код, корректирующий однократную ошибку, необходимо расширить ее до m разрядов, т. е. (n n) → (n m). Для этого справа приписывается матрица контрольных разрядов, содержащая k столбцов (m = n + k).

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

К матрице А предъявляются следующие требования:

1. Поскольку будет синтезироваться избыточный равномерный систематический код, позволяющий обнаружить и скорректировать однократную ошибку, то расстояние между кодовыми комбинациями должно быть: d 3. Поскольку единичная матрица расширилась на k разрядов, то каждая строка дополнительно приписываемой части матрицы должна иметь не менее чем (d - 1) единиц, поскольку уже одну единицу содержит каждая строка единичной матрицы.
2. Различие между строками в приписываемой матрице должно быть не менее чем в (d - 2) разрядах, т.к. различие в единичной матрице в двух строках уже есть.

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

Проверочная матрица строится следующим образом: к единичной матрице размером k k слева приписывается матрица из n столбцов и k строк (n k). При этом строка приписываемой матрицы является столбцом дополнительной матрицы из матрицы A.

К матрице П предъявляется следующее требование.

Сумма единиц по модулю 2 любой строки проверочной матрицы должна быть четным числом (или во всех строках нечетная), т.к. сумма по модулю 2 равна нулю при четности. Это является условием обнаружения и локализации ошибки в любой кодовой комбинации. Локализация ошибки основана на индивидуальной кодовой комбинации (опознавателях), и эта кодовая комбинация представляется в виде f₀ f₁ f₂ … f_k-1 (количество контрольных разрядов)

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

Согласно условию задачи количество отображенных чисел (сообщений) М = 10. Для представления этих чисел n = 4, k = 3. Составим производящую матрицу.

Выполняется условие: не менее (d-1) единиц. На основании этой матрицы можно построить 16 кодовых комбинаций с разрядностью . Составим 10 кодовых комбинаций, которые будут необходимы для индикации требующихся цифр. Пусть это будут следующие комбинации:

Первые четыре кодовые комбинации – это строки матрицы А. Последние 6 кодовых комбинаций являются суммами строк по модулю 2, соответственно: , , , , , .

Строим проверочную матрицу

Проверочная матрица показывает, что k₀ контролирует 1,2,3 разряды, k₁ – 0,2,3 разряды, k₂ – 0,1,3 разряды.

На основании проверочной матрицы можно составить уравнения кодов-опознавателей местоположения ошибки:

(*)

Последовательность f₀ f₁ f₂ – является кодом ошибочной или безошибочной комбинации

Если кодовая комбинация не содержит ошибок, то согласно (*) все позиции будут содержать нули, следовательно, получится код f₀ f₁ f₂ = 0 0 0.

Рассмотрим подчеркнутую кодовую комбинацию 1 0 1 0 1 0 1 и начнем последовательно вводить ошибки.

Вводим ошибку в разряд a₀ и получаем код опознавателя ошибки в этом разряде:

, f₀ f₁ f₂ = 0 1 1.

Затем вводим ошибку в разряд а₁ и получаем код опознавателя ошибки в этом разряде; затем в вводим ошибку а₂ и получаем код опознавателя ошибки в этом разряде и т.д.

Например, ошибка в разряде а₃:

, f₀ f₁ f₂ = 1 1 1

В итоге получаем таблицу кодов опознавателей ошибок:

Проверим получившийся результат. Пусть передали комбинацию 1000011, а получили 100 1 011. Определяем код опознавателя:

, f₀ f₁ f₂ = 1 1 1 следовательно, ошибка в разряде а_{3 .}

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

Дата добавления: 2015-07-02