125

Лабораторная работа 7

Код с проверкой на четность и циклический код

1. Введение

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

Цель настоящей работы – изучение принципов построения кодера и декодера, а также экспериментальное исследование корректирующей способности кодов на примере кода с проверкой на четность (7,6) и циклического кода (7,4).

2. Сведения из теории корректирующих кодов

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

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

Идея рационального введения избыточности в передаваемый сигнал реализуется применением корректирующих кодов. Наиболее часто применяют блочные корректирующие коды. Информационная кодовая комбинация (КК) с выхода источника сообщений содержит k разрядов a=a₁, a₂,…, a_k, где a_i=0;1. Считается, что она не имеет избыточности. Будем рассматривать только двоичные коды (основание кода m=2). Число всех возможных КК от источника N=m^k=2^k. В пространстве двоичных КК вводят понятие расстояния Хэмминга. Расстоянием Хэмминга d_ij называет число символов, в которых кодовые комбинации a_i и a_j отличаются друг от друга. Для двоичного кода расстояние d_ij удобно определять как вес (количество единиц) кодовой комбинации, полученной в результате суммирования a_i и a_j по модулю два (mod 2). Суммирование по mod 2 выполняется по правилу

00=0, 01=1, 10=1, 11=0.

(7.1)

Вес КК равен количеству единиц, содержащихся в ней.

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

1) в виде r лишних, избыточных символов; тогда длина КК увеличивается и становится равной п=k+r. При этом избыточность кода оценивают как R=r/п;

2) выделением из общего числа N кодовых комбинаций N_p разрешенных, используемых для передачи. Остальные N_з=N–N_p комбинаций являются запрещенными. Величина избыточности равна Ошибки в канале связи обычно (но не обязательно) переводят разрешенную КК в запрещенную и таким образом обнаруживаются.

Отличие (расстояние) между переданной и принятой КК называют кратностью ошибки q. Корректирующие коды могут обнаруживать и даже исправлять некоторые ошибки, возникающие при передаче по каналу связи. Для характеристики корректирующих свойств кода вводят понятие кодового расстояния, т.е. минимального расстояния Хэмминга для данного кода

dкод=min dij, ij.

(7.2)

При грамотном введении избыточности в передаваемый сигнал минимальное расстояние увеличивается и становится d_код>l. Связь между кратностью обнаруживаемой ошибки q_o, кратностью исправляемой ошибки q_и и величиной кодового расстояния определяется так:

dкодqo+1, dкод2qи+1.

(7.3)

Таким образом, для обнаружения любой однократной ошибки (q_o=1) корректирующий код должен иметь хотя бы d_код =2, а для исправления любой однократной ошибки (q_и=1) нужно иметь d_код =3.