Кодирования сообщения избыточный семиразрядный код Хемминга

 Введение:

В настоящее время самым дорогим ресурсом на планете считается информация. При всем разнообразии современной информации, вся она на том или ином этапе своего существования преобразуется в последовательность чисел или, короче говоря, в последовательность нулей и единичек. Именно в такой форме информация (данные, сигналы и т. п.) передается по линиям связи (передача в пространстве), хранится на носителях (передача во времени).

К несчастью, в процессе передачи информации она может быть искажена. Здесь речь идет не о преднамеренных искажениях, а лишь о так называемых «помехах», т. е. или случайных возмущениях в линиях связи, или случайных повреждениях носителя. Помехи существуют в силу объективных причин и устранить помехи невозможно. Однако искажение информации не безобидно, ведь искажению может подвергнуться важная и нужная информация. Передача информации, прежде всего, необходима для управления механизмом, системой, обществом. В результате искажения может быть нарушена деятельность жизненно важных систем, отданы неверные приказы или не выполнены некие действия. В методах передачи цифровой информации эти технологии получили название: «помехозащищенное кодирование». Помехозащищенное кодирование возможно только за счет передачи дополнительной информации, т. е. любая попытка защититься от помех требует передачи большего количества информации, чем исходная. Основная задача при разработке помехозащищенных алгоритмов минимизировать эту дополнительную информацию.

 Кодирование сообщения, которое требуется передать по каналу связи, заключается в том, что в кодовую комбинацию помимо k разрядов исходного кода (информационных разрядов) дополнительно включают r избыточных (контрольных) разрядов. В результате кодирования передаваемому сообщению будет соответствовать не k-разрядная кодовая комбинация значений исходного двоичного кода, а (k + r)-разрядное двоичное число.

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

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

Исходные данные:

Кодируемое передаваемое сообщение: 11012=1310.

Используемый для кодирования сообщения избыточный код: Семиразрядный код Хемминга.

1 Построение кода для передаваемого сообщения

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

При кодировании семиразрядным кодом Хемминга к исходному двоичному четырех разрядному коду добавляем 3-х разрядное двоичное число, состоящее из контрольных разрядов.

При использовании указанного кода определим значения контрольных разрядов:

r1 = k4⊕k3⊕k1 = 1 ⊕ 1 ⊕ 1 = 1;

r2 = k4⊕k2⊕k1 = 1 ⊕ 0⊕ 1= 0;

r3 = k3⊕k2⊕k1 = 1 ⊕ 0 ⊕ 1 = 0

Руководствуясь правилами построения кода Хэмминга, составим искомую кодовую комбинацию: r1r2k4 r3k3k2k1=1010101.

Значения разрядов синдрома кодовой комбинации будут равны:

i1 = r1[pic 1] k4[pic 2] k3[pic 3] k1 =1 ⊕ 1 ⊕ 1 ⊕ 1= 0;

i2 = r2[pic 4] k4[pic 5]k2[pic 6] k1 = 0 ⊕ 1 ⊕ 0 ⊕ 1= 0;

i3 = r3[pic 7]k3[pic 8]k2[pic 9]k1  = 0 ⊕ 1 ⊕  0 ⊕ 1= 0

2 Расчет корректирующих способностей заданного кода