Коды с обнаружением и исправлением ошибок

Метод максимального правдоподобия для исправлениея кодов

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

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

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

понедельник, 3 июня 13 г.

Кодовое расстояние

Кодовым расстоянием или просто расстоянием кода V называется минимальное расстояние между двумя различными кодовыми словами

dv	= min d(x, y), x ≠ y, x, y V
	x,y

Для двоичного кода V под расстоянием понимается расстояние Хэмминга.

понедельник, 3 июня 13 г.

Кодовое расстояние

Теорема 1. Код V исправляет все комбинации из t или менее ошибок, если и только если кодовое расстояние не меньше, чем 2t +1, т. е.

dv ≥ 2t +1

понедельник, 3 июня 13 г.

Кодовое расстояние

Теорема 2. Код V обнаруживает все комбинации из t или менее ошибок, если и только если кодовое расстояние не меньше

dv ≥ t +1

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

понедельник, 3 июня 13 г.

Кодовое расстояние

Пример. В качестве примера попробуем построить код с кодовым словом длины 5, который имеет 3 информационных символа и исправляет одну ошибку. Так как информационных символов три, то различных кодовых слов должно быть 23 = 8. Согласно теореме 1.1 расстояние между двумя различными кодовыми словами должно быть не меньше 2×1 + 1 = 3. Включим в код V слово 00000. Тогда все остальные кодовые слова имеют вес не менее 3. После включения в код V любого слова веса 3, ни одно слова веса 3 в код добавлено быть не может, так как расстояние между любыми двумя словами веса 3 равно 2. По той же причине слово 11111 веса 5 также не принадлежит коду V. Остаются 5 слов веса

4, которых не достаточно, чтобы иметь 8 кодовых слов.

понедельник, 3 июня 13 г.

ЛИНЕЙНЫЕ БЛОКОВЫЕ КОДЫ

Булево пространство Bn , B = {0,1}, представляет собой множество двоичных векторов длины n.

Операция сложения по модулю 2 является групповой операцией, и	и
множество Bn представляет собой линейное пространство с операцией
умножением на скаляр из множества {0,1}.

Линейным двоичным или групповым кодом называется подпространство линейного пространства Bn.

Пример. Рассмотрим множество V = {000, 011, 100, 111}. Непосредственной

проверкой можно убедиться, что сумма любых двух слов множества является элементом множества, т. е. V - линейный код.

понедельник, 3 июня 13 г.

ЛИНЕЙНЫЕ БЛОКОВЫЕ КОДЫ

понедельник, 3 июня 13 г.

ЛИНЕЙНЫЕ БЛОКОВЫЕ КОДЫ

Теорема 3. Кодовое расстояние линейного кода равно минимальному весу ненулевого кодового слова.

Доказательство. Пусть расстояние кода совпадает с расстоянием между кодовыми словами x и y. Так как V линейный код, то x + y = z тоже принадлежит коду V; т. о. dV = w(z). Так как нулевое слово принадлежит коду V, то код не содержит ненулевых слов веса меньше dV.

Теорема 4. Мощность линейного (n,k) - кода равна 2k.

Доказательство. Каждое кодовое слово есть линейная комбинация базисных

кодовых слов. Число различных линейных комбинаций равно, т. е. |V| ≤ 2k. Две линейные комбинации с различными коэффициентами не совпадают, так как базисные векторы линейно независимы. Поэтому |V| = 2k.

понедельник, 3 июня 13 г.

Матричное описание порождающих кодов: Порождающая матрица

Матрица G состоящая из всех базисных векторов линейного кода V называется порождающей матрицей кода V. Строки матрицы G линейно независимы, и число k строк равно размерности кода. Таким образом, порождающая матрица (n,k) - кода имеет размерность k×n. .

В качестве примера рассмотрим порождающую матрицу:

Соответствующий (5,3) - код V = {00000, 10011, 11001, 11100, 01010, 01111, 00101, 10110} содержит 23 = 8 кодовых слов.

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

понедельник, 3 июня 13 г.

Матричное описание порождающих кодов: Порождающая матрица

Так как множество базисных векторов линейного пространства можно выбрать различными способами, то для одного и того же кода существуют различные порождающие матрицы. Соответственно выбор кодового слова для каждого информационного набора зависит от выбора порождающей матрицы. Например, если в качестве порождающей матрицы кода V = {00000, 10011, 11001, 11100, 01010, 01111, 00101, 10110} выбрать другую матрицу:

,

то информационное слово i = (0 1 1) будет преобразовано в кодовое слово равно c = 0 × 0 1 1 1 1 + 1 × 0 0 1 0 1 + 1 × 1 0 1 1 0 = 1 0 0 1 1.

понедельник, 3 июня 13 г.