Коды Хэмминга. Кодом Хэмминга называется (n, k) – код, который задается матрицей проверок H(n,k), имеющей строк и столбцов

Кодом Хэмминга называется (n, k) – код, который задается матрицей проверок H(n,k), имеющей Коды Хэмминга. Кодом Хэмминга называется (n, k) – код, который задается матрицей проверок H(n,k), имеющей строк и столбцов - student2.ru строк и Коды Хэмминга. Кодом Хэмминга называется (n, k) – код, который задается матрицей проверок H(n,k), имеющей строк и столбцов - student2.ru столбцов, причем столбцами H(n,k) являются все различные ненулевые двоичные последовательности длины m (m – разрядные двоичные числа от 1 до Коды Хэмминга. Кодом Хэмминга называется (n, k) – код, который задается матрицей проверок H(n,k), имеющей строк и столбцов - student2.ru ).

Длина кодовой комбинации кода Хэмминга равна Коды Хэмминга. Кодом Хэмминга называется (n, k) – код, который задается матрицей проверок H(n,k), имеющей строк и столбцов - student2.ru .

Число информационных элементов определяется как Коды Хэмминга. Кодом Хэмминга называется (n, k) – код, который задается матрицей проверок H(n,k), имеющей строк и столбцов - student2.ru .

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

Зная вид матрицы H(n,k), можно определить корректирующие свойства (n, k) – кода Хэмминга. Так как все столбцы матрицы проверок различны, то никакие два столбца H(n,k) не являются линейно зависимыми. Наряду с этим, для любого числа m всегда можно указать три столбца матрицы H(n,k), которые линейно зависимы, например, столбцы, соответствующие числам 1, 2, 3. Следовательно, для любого (n, k) – кода Хэмминга dmin=3.

При фиксированном числе Коды Хэмминга. Кодом Хэмминга называется (n, k) – код, который задается матрицей проверок H(n,k), имеющей строк и столбцов - student2.ru можно построить код Хэмминга любой длины ( Коды Хэмминга. Кодом Хэмминга называется (n, k) – код, который задается матрицей проверок H(n,k), имеющей строк и столбцов - student2.ru ) путем укорочения (n, k) – кода. Укорочение не уменьшает минимальное кодовое расстояние. В силу того, что для любого числа n существует код Хэмминга, любой групповой код с исправлением одиночных ошибок принято называть кодом Хэмминга.

Например определим параметры кодов Хэмминга для различных значений m. Результаты представим в виде таблицы.

m Коды Хэмминга. Кодом Хэмминга называется (n, k) – код, который задается матрицей проверок H(n,k), имеющей строк и столбцов - student2.ru k Коды Хэмминга. Кодом Хэмминга называется (n, k) – код, который задается матрицей проверок H(n,k), имеющей строк и столбцов - student2.ru
0,33
0,57
0,74
0,84
0,91
0,95

и т.д.

Очевидно, что минимальная длина кода Хэмминга, имеющего практическое значение, есть 3. При увеличении n отношение Коды Хэмминга. Кодом Хэмминга называется (n, k) – код, который задается матрицей проверок H(n,k), имеющей строк и столбцов - student2.ru возрастает и стремится к 1.

Рассмотрим код Хэмминга (7,4). Матрица проверок этого кода состоит из 7 трехразрядных двоичных чисел от 1 до 7:

Коды Хэмминга. Кодом Хэмминга называется (n, k) – код, который задается матрицей проверок H(n,k), имеющей строк и столбцов - student2.ru .

Из рассмотрения этой матрицы видно, что минимальное число линейно зависимых столбцов равно 3( к примеру 1, 2 и 3), следовательно, dmin=3.

В том случае, когда столбцы матрицы H(n,k) – кода Хэмминга есть упорядоченная запись m – разрядных двоичных чисел, декодирование осуществляется оригинальным образом. В результате вычисления проверочного соотношения для кодовой комбинации Коды Хэмминга. Кодом Хэмминга называется (n, k) – код, который задается матрицей проверок H(n,k), имеющей строк и столбцов - student2.ru , имеющей одиночную ошибку, получается синдром Коды Хэмминга. Кодом Хэмминга называется (n, k) – код, который задается матрицей проверок H(n,k), имеющей строк и столбцов - student2.ru в точности равный номеру элемента, в котором произошла ошибка.

Действительно, если ei содержит одну единицу в разряде, соответствующем ошибочному элементу, то при умножении на матрицу НТ все строки матрицы НТ, соответствующие нулям в ei, обращаются в нули, и лишь строка, соответствующая “1” в ei сохраняет свой вид (т.е. порядковый номер элемента в двоичной записи) в ответе.

Например приемник зарегистрировал комбинацию Коды Хэмминга. Кодом Хэмминга называется (n, k) – код, который задается матрицей проверок H(n,k), имеющей строк и столбцов - student2.ru . Вычисление синдрома дает

Коды Хэмминга. Кодом Хэмминга называется (n, k) – код, который задается матрицей проверок H(n,k), имеющей строк и столбцов - student2.ru ,

т.е. ошибка в четвертом элементе и кодовая комбинация кода (7,4), которая была передана, имеет вид: Коды Хэмминга. Кодом Хэмминга называется (n, k) – код, который задается матрицей проверок H(n,k), имеющей строк и столбцов - student2.ru

Путем несложных преобразований из (n, k) – кода Хэмминга с dmin=3 можно получить (n+1, k) – код Хэмминга с dmin=4.

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

Матрица проверок для (n+1, k) – кода Хэмминга с dmin=4 получается из матрицы проверок (n, k) – кода с dmin=3 путем введения дополнительной строки из (n+1)-ой единицы.

Так как размерность матрицы проверок кода с dmin=4 должна быть равна Коды Хэмминга. Кодом Хэмминга называется (n, k) – код, который задается матрицей проверок H(n,k), имеющей строк и столбцов - student2.ru , то к каждой строке матрицы проверок кода с dmin=3, необходимо добавить один нулевой элемент для того, чтобы не нарушить введенные ранее проверки. Матрица проверок для (n+1, k) – кода dmin=4 имеет вид:

Коды Хэмминга. Кодом Хэмминга называется (n, k) – код, который задается матрицей проверок H(n,k), имеющей строк и столбцов - student2.ru ,

где H(n,k) = матрица проверок исходного кода с dmin=3.

Рассмотренная процедура, приведшая к удлинению кодовой комбинации на один разряд при увеличении dmin на 1 единицу, получила название удлинения кода (1- удлинение).Удлинению могут быть подвергнуты и другие коды, например, коды Рида-Соломона.

Пример 5.16. Построить код Хэмминга (8,4) с dmin=4 на основе матрицы проверок кода (7,4).

Известно:

Коды Хэмминга. Кодом Хэмминга называется (n, k) – код, который задается матрицей проверок H(n,k), имеющей строк и столбцов - student2.ru

По виду матрицы Коды Хэмминга. Кодом Хэмминга называется (n, k) – код, который задается матрицей проверок H(n,k), имеющей строк и столбцов - student2.ru можно сделать вывод о том, что в коде (7,4) осуществляется 3 независимые проверки на четность.

Каждая из строк определяет элементы кодовой комбинации, охваченные одной проверкой.

Таким образом, матрице Коды Хэмминга. Кодом Хэмминга называется (n, k) – код, который задается матрицей проверок H(n,k), имеющей строк и столбцов - student2.ru соответствует следующая система проверочных соотношений:

Коды Хэмминга. Кодом Хэмминга называется (n, k) – код, который задается матрицей проверок H(n,k), имеющей строк и столбцов - student2.ru

Для того, чтобы получить код (8,4) с dmin=4 вводим еще одну проверку по всем элементам кодовой комбинации, а результат этой проверки записывается в виде дополнительного 8-го элемента:

Коды Хэмминга. Кодом Хэмминга называется (n, k) – код, который задается матрицей проверок H(n,k), имеющей строк и столбцов - student2.ru

или

Коды Хэмминга. Кодом Хэмминга называется (n, k) – код, который задается матрицей проверок H(n,k), имеющей строк и столбцов - student2.ru .

Этой проверке соответствует дополнительная (четвертая) строка в матрице Н(8,4), состоящая из восьми единиц. Для того чтобы не нарушить три предыдущие проверки на месте восьмого элемента в трех первых строках матрицы Н(8,4) на месте восьмого элемента, проставляем нули. Итак, матрица проверок кода (8,4) получена в виде:

Коды Хэмминга. Кодом Хэмминга называется (n, k) – код, который задается матрицей проверок H(n,k), имеющей строк и столбцов - student2.ru .

Определим известным способом dmin (8,4) – кода. Из рассмотрения тех столбцов, сумма которых давала нулевой столбец в (7,4) – коде, видно, что с добавлением 4-ой строки они перестали быть линейно зависимыми. Теперь уже число линейно зависимых столбцов должно быть четным и минимум 4, например, 3 первые столбца и последний. Таким образом, для полученного кода Хэмминга (8,4) dmin=4.

До сих пор мы еще не разделили элементы кодовой комбинации на информационные и проверочные. Наиболее рационально, по-видимому, это можно сделать следующим образом. Желательно, чтобы каждое проверочное соотношение однозначно определяло проверочный элемент как результат проверки на четность некоторой совокупности информационных элементов. В таком случае мы получили бы возможность определять значение проверочного элемента наиболее простым образом – решением одного линейного уравнения с одним неизвестным. Для этого при упорядоченной записи столбцов матрицы H(n,k) в качестве проверочных элементов необходимо брать элементы с номерами 2i, где i изменяется от 0 до m-1, так как именно эти столбцы содержат только по одной единице. Последнее свидетельствует о том, что элементы с номерами 2i входят только в одну проверку и, следовательно, они могут быть взяты в качестве проверочных.

Пример 5.17. Определить местоположение проверочных элементов к коде Хэмминга (7,4).

По виду матрицы Коды Хэмминга. Кодом Хэмминга называется (n, k) – код, который задается матрицей проверок H(n,k), имеющей строк и столбцов - student2.ru , приведенной в предыдущем примере, в качестве проверочных элементов выбираем элементы, которым соответствуют столбцы, содержащие только по одной единице, т.е. первый, второй и четвертый. Следовательно, 4 информационных элемента кода (7,4) должны занимать места 3, 5, 6 и 7-го разрядов. Приведенная в предыдущем примере система проверочных соотношений позволяет определить значение каждого из проверочных элементов по значениям информационных элементов, т.е. по значению элементов простого кода, который необходимо закодировать кодом Хэмминга

Коды Хэмминга. Кодом Хэмминга называется (n, k) – код, который задается матрицей проверок H(n,k), имеющей строк и столбцов - student2.ru

Зная места проверочных элементов, легко привести матрицу H(n,k) кода Хэмминга к канонической форме.

Для этого необходимо столбцы с номерами 2i, где Коды Хэмминга. Кодом Хэмминга называется (n, k) – код, который задается матрицей проверок H(n,k), имеющей строк и столбцов - student2.ru при упорядоченной записи столбцов переместить на места m первых столбцов в порядке убывания номеров. В общем виде такая перестановка столбцов в матрице H(n,k) приводит к эквивалентному (n, k) – коду. В случае же кодов Хэмминга естественной длины код получается даже не эквивалентный, а в точности совпадающий с исходным кодом.

Пример 5.18. Преобразовать матрицу Коды Хэмминга. Кодом Хэмминга называется (n, k) – код, который задается матрицей проверок H(n,k), имеющей строк и столбцов - student2.ru к канонической форме.

Коды Хэмминга. Кодом Хэмминга называется (n, k) – код, который задается матрицей проверок H(n,k), имеющей строк и столбцов - student2.ru

Переставим столбцы: 4-ый на место 1-го, 1-ый на место 3-го, а 3-ий на место 4-го:

Коды Хэмминга. Кодом Хэмминга называется (n, k) – код, который задается матрицей проверок H(n,k), имеющей строк и столбцов - student2.ru .

Это и есть каноническая форма матрицы Коды Хэмминга. Кодом Хэмминга называется (n, k) – код, который задается матрицей проверок H(n,k), имеющей строк и столбцов - student2.ru . Сравнение ее с исходной матрицей Коды Хэмминга. Кодом Хэмминга называется (n, k) – код, который задается матрицей проверок H(n,k), имеющей строк и столбцов - student2.ru показывает, что местам информационных элементов в канонической форме соответствуют столбцы с номерами 3, 5, 6, 7, а местам проверочных элементов - столбцы 4, 2, 1.

При этом связи между информационными и избыточными элементами сохранились с учётом их перестановки:

Коды Хэмминга. Кодом Хэмминга называется (n, k) – код, который задается матрицей проверок H(n,k), имеющей строк и столбцов - student2.ru

Порождающую матрицу G(n, k) для кода Хэмминга можно получить из матрицы H(n,k), используя теорему 5.3:

Коды Хэмминга. Кодом Хэмминга называется (n, k) – код, который задается матрицей проверок H(n,k), имеющей строк и столбцов - student2.ru

Кодирующие и декодирующие устройства для этого класса кодов будут рассмотрены при изучении циклических кодов.

Оценим эффективность кодов Хэмминга.

а) Коды Хэмминга с dmin=3

Такие коды используются либо для исправления ошибки кратности t=1, либо для гарантийного обнаружения ошибок кратности S=2. Соответственно, вероятность ошибки для этих случаев в канале с группированием ошибок равна:

.

б) Коды Хэмминга с dmin=4.

Для таких кодов возможны два режима – исправление однократных ошибок и обнаружение ошибок и только обнаружение ошибок. Вероятность ошибки для этих режимов в случае группирования ошибок равна:

Выигрыш по достоверности по сравнению с простым кодом той же длины составляет:

Наши рекомендации