Студопедия
Случайная страница | ТОМ-1 | ТОМ-2 | ТОМ-3
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатика
ИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханика
ОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторика
СоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансы
ХимияЧерчениеЭкологияЭкономикаЭлектроника

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

Читайте также:
  1. Коды Хэмминга
  2. Расширенные коды Хэмминга

Общие сведения

К кодам Хэмминга относится семейство групповых систематических линейных блочных помехоустойчивых кодов с параметрами (n; k). Число проверочных символов r = n-k. Для этих кодов выполняется равенство 2r= 2n-k=1+n или n=2n-k-1= 2r-1. Кодами Хэмминга являются коды (3;1), (7;4),(15;11), (31;26). Кодовое расстояние кодов Хэмминга d0=3 и, соответственно, они могут гарантированно обнаруживать две ошибки и исправлять одну ошибку. Для построения кода Хэмминга нет необходимости задавать все 2k разрешенные кодовые комбинации. Достаточно выбрать определенным образом k исходных разрешенных кодовых комбинаций и затем путем их посимвольного суммирования по модулю два в различных сочетаниях получить остальные (2k-k) разрешенные последовательности. Вышеуказанные исходные кодовые комбинации называют базисными. При их выборе должны выполняться следующие условия:

а) исходные (базисные) кодовые последовательности должны выбираться различными;

б) нулевая кодовая последовательность (состоящая из одних нулей) не должна выбираться;

в) исходные кодовые комбинации должны быть линейно-независимыми и образовывать алгебраическую группу по отношению к операции суммирования по модулю два;

Примечание: Линейно-независимыми являются ненулевые комбинации А1, А2…,Аk, если выполняется условие где сi=0 или 1, причем хотя бы один из коэффициентов сi≠0

г) вес (число единиц) каждой исходной кодовой последовательности должен быть не менее d0;

д) вес проверочной части исходной кодовой последовательности должен быть не менее d0-1;

е) расстояние Хэмминга d в любых парах исходных кодовых последовательностей должно быть не менее d0;

ж) минимальный вес исходной кодовой последовательности должен быть равен кодовому расстоянию d0.

 

Порождающая матрица

Обычно набор из k линейно независимых кодовых последовательностей, формирующих СЛБ (n; k)-код, записывают в виде матрицы, называемой производящей или порождающей (генерирующей) матрицей, обозначаемой как Gk,n. Матрица Gk,n содержит k строк и n столбцов, так как ее размерность (ранг) – (k n) определяется параметрами кода n, k и r. В общем виде порождающая матрица может быть записана так:

Gk,n = ,

где буквами а обозначены информационные символы, а буквами b – проверочные.

Для кодирования с помощью матрицы Gk,n ее приводят к каноническому приведенно-ступенчатому виду. Каноническая матрица Gk,n содержит две подматрицы: информационную − рангом (k k) и проверочную − рангом (k r). Информационную подматрицу представляют в виде единичной квадратной матрицы Ik, у которой по главной диагонали стоят единицы, а все остальные элементы − нули. Единичная матрица Ik имеет вид:

 

Ik = Ik,k= (10)

Используя матрицу (10), можно сформировать любую кодовую комбинацию простого (безызбыточного) k – разрядного кода. Возможное число комбинаций равно 2k.

Для составления канонической матрицы Gk,n к информационной единичной матрице Ik приписывают справа проверочную подматрицу G*, формируемую с учетом требований, предъявляемых к исходным базисным комбинациям помехоустойчивого кода. При этом необходимо учитывать следующие свойства СЛБК: чем больше логических «1» в приписываемых строках проверочной подматрицы, тем большей корректирующей способностью обладает разрабатываемый код и тем сложнее его реализация. В качестве примера построим каноническую порождающую матрицу для кода Хэмминга (7;4;3), в котором число информационных символов k=4, общее число символов n =7.

Информационная единичная подматрица этого кода имеет вид:

Ik= I4,4= (11)

Допишем к каждой строке матрицы символы проверочной подматрицы, причем вес приписываемой строки должен быть не менее d0-1=3-1=2, т.е. необходимо к каждой строке дописать по две «1». В этом случае вес каждой строки матрицы Gk,n будет равен Wстр= d0=3. Число столбцов в матрице Gk,n окажется равным n=4+2=6, что не соответствует заданному коду, и, кроме того, расстояние Хэмминга в любых парах базисных слов d =2, что менее требуемого d0=3. Поэтому в проверочную часть каждой строки дописываем еще один (третий) символ «0» или «1». Окончательно матрица Gk,n примет вид:

 

(12)

Поскольку базисные исходные комбинации могут быть выбраны произвольным образом, то можно построить множество матриц Gk,n с одним и тем же кодовым расстоянием. Так, для кода Хэмминга (7;4;3) существует 29 вариантов порождающих матриц вида (5.5). Коды, обладающие одними и теми же параметрами (n;k;d0), но задаваемые различными порождающими матрицами, получили название эквивалентных кодов. В этих кодах различная зависимость проверочных символов от информационных.

 

Формирование кодовых комбинаций с использованием порождающей матрицы

Имея каноническую порождающую матрицу Gk,n и исходный информационный блок Аk из k двоичных символов, разрешенную кодовую комбинацию А можно получить путем умножения информационного блока Аk на матрицу Gk,n:

 

А = Аk Gk,n (13)

 

Пример 7 Закодировать кодом Хэмминга (7;4) информационную последовательность Аk=0101 с использованием порождающей матрицы (12). Воспользуемся выражением (13):

А = Аk G=

Для нахождения значения первого (старшего) разряда в кодовой комбинации поразрядно умножаем входную информационную последовательность Аk на первый столбец матрицы G4,7 и полученные символы суммируем по модулю два:

 

Полученный символ совпадает с символом первого разряда входной последовательности Аk, поскольку в G4,7 информационная подматрица единичная. Аналогично второй, третий и четвертый символы повторяют соответствующие символы входной последовательности Аk. Поэтому достаточно рассчитать только проверочные символы кодового слова. Найдем пятый символ, для чего Аk умножим на пятый столбец матрицы (12) и полученные символы просуммируем по модулю два:

   

Аналогично рассчитаем шестой и седьмой символы кодового слова:

      и

В итоге получаем семиразрядную кодовую последовательность, первые четыре символа которой совпадают с информационными: А=0101010.

Рассмотренный способ формирования кодовых последовательностей довольно сложен. Более простую процедуру кодирования и декодирования линейных (n; k) кодов дает применение проверочной матрицы Нr,n.

 

Проверочная матрица

Для систематического линейного блочного кода проверочную матрицу Нr,n, содержащую r строк и n столбцов, можно построить на основе приведено-ступенчатой порождающей матрицы Gk,n путем транспонирования ее проверочной подматрицы G* и последующего дописывания единичной проверочной подматрицы Ir. Транспонирование подматрицы G* проводится следующим образом: каждая из строк проверочной подматрицы G* записывается последовательно в виде соответствующего столбца проверочной матрицы: т.е. первая строка записывается в виде первого столбца, вторая строка в виде второго столбца и т.д. В результате получают проверочную подматрицу Н* проверочной матрицы Нr,n. Подматрица Н* имеет ранг (r k). К ней дописывается единичная проверочная подматрица Ir с рангом (r r). В итоге проверочная матрица Нr,n имеет ранг (r n).

Каждой порождающей матрице СЛБК соответствует своя проверочная матрица. Во всех случаях должно выполняться условие:

G HT=0 (14)

где HT − транспонированная проверочная матрица.

Это свойство проверочной матрицы используется при декодировании СЛБК.

Для (7;4)-кода Хэмминга, задаваемого порождающей матрицей (5.5), приведено- ступенчатая проверочная матрица имеет вид:

(15)

 

Формирование кодовых комбинаций с использованием проверочной матрицы

Каждая из r строк проверочной матрицы Нr,n определяет правила формирования одного из проверочных символов разрешенной кодовой комбинации. На то, какой именно формируется символ и из какой строки подматрицы Н* его получают, указывает единица в столбце единичной подматрицы Ir. Конкретное значение проверочного символа (« или «) определяется путем суммирования по модулю два тех информационных символов входной комбинации Аk, номера которых совпадают с ненулевыми (единичными) позициями соответствующей строки проверочной подматрицы Н*. Таким образом формируются проверочные уравнения для любого конкретного СЛБК. Система проверочных уравнений для (7;4)- кода с проверочной матрицей (15) имеет вид:

(16)

 

Пример 8 Закодировать кодом (7;4) информационную последовательность Аk =0101, что и в примере 9, с использованием проверочной матрицы (15). Для нахождения проверочных символов воспользуемся системой проверочных уравнений (16):

В итоге получаем кодовую последовательность А=0101010, совпадающую с результатом примера 9

Проверочная матрица не только задает правила кодирования линейного кода, но и определяет схему кодирующего устройства. Электрическая структурная схема кодирующего устройства для кода, задаваемого проверочной матрицей (15), приведена на рисунке 4. Разрешенная кодовая комбинация кода Хэмминга формируется за один такт после поступления входных информационных символов.

 

 

Рисунок 4 − Электрическая структурная схема кодера линейного кода (7;4)

 


Дата добавления: 2015-08-13; просмотров: 588 | Нарушение авторских прав


Читайте в этой же книге: КОДИРОВАНИЕ СООБЩЕНИЙ | КОДИРОВАНИЕ СООБЩЕНИЙ В ЦИФРОВЫХ СИСТЕМАХ ПЕРЕДАЧИ | Общие сведения | Кодирование неравномерными кодами | Основные принципы помехоустойчивого кодирования | Классификация помехоустойчивых кодов | Групповые систематические линейные блочные коды | Общие сведения | Порождающий полином циклического кода | Проверочный полином циклического кода |
<== предыдущая страница | следующая страница ==>
Коды с четным числом единиц| Расширенные коды Хэмминга

mybiblioteka.su - 2015-2024 год. (0.013 сек.)