Радиотехническая система передач

БЕЛОРУССКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИНФОРМАТИКИ И РАДИОЭЛЕКТРОНИКИ

Кафедра радиотехнических систем

РЕФЕРАТ

На тему:

«Параметры кодов. Контроль, обнаружение и исправление ошибок»

МИНСК, 2008

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

1 Основание кода – число элементов множества , выбранное для построения кода. Например, если:

а) , то для троичного кода;

б) для двоичного кода.

Практически .

Замечание – Эффективность каналов передачи (хранения) информации возрастает с переходом на недвоичные коды.

2 Длина кода (значность) – число символов кодового слова.

Определение 2. Последовательности элементов (символов) длиной называются кодовыми словами или кодовыми векторами. Говорят, что слово

имеет длину ; ,

Параметр определяет следующие особенности класса кодов. Коды бывают:

а) равномерные (блоковые), ;

б) неравномерные, ;

в) бесконечные, . К бесконечным относят коды:

свёрточные;

цепные;

непрерывные.

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

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

На рисунке 1.1 показаны структуры кодирования блоковыми и непрерывными кодами.

k-битовый n-битовый n-битовый k-битовый

блок блок блок блок

Блоковый код

k0 битов/кадр n0 битов/кадр n0 битов/кадр k0 битов/кадр

Непрерывный код

Рисунок 1.1

3 Размерность кода – число информационных позиций кодового слова.

4 Мощность кода – число различных кодовых последовательностей (комбинаций), используемых для кодирования.

– максимальное число кодовых комбинаций при заданных и . Например, ; ; .

Определение 3. Код, у которого используются все комбинации, называется полным (безизбыточным).

Определение 4. Если число кодовых слов кода , то код называется избыточным.

Пример – Пусть , , .

Код – избыточный; .

5 Число проверочных (избыточных) позиций кодового слова .

Пусть , , . Тогда на длине слова из семи символов – три избыточных.

6 Скорость передачи кода . Для приведенного примера .

7 Кратность ошибки . Параметр указывает, что все конфигурации из

или менее ошибок в любом кодовом слове могут быть исправлены.

8 Расстояние Хэмминга между двумя векторами (степень удаленности любых кодовых последовательностей друг от друга) .

Определение 5. Если и кодовые векторы, то расстояние Хэмминга равно числу позиций, в которых они различаются. Может обозначаться и как – . Например, ;.

Замечание – С позиции теории кодирования показывает, сколько символов в слове надо исказить, чтобы перевести одно кодовое слово в другое.

9 Кодовое расстояние (минимальное расстояние кода) .

Определение 6. Наименьшее значение расстояния Хэмминга для всех пар кодовых последовательностей кода называют кодовым расстоянием. , где ; ; .

Определение 7. Код значности , размерности и расстояния называется - кодом.

Пример – Можно построить следующий код:

; ; ; .

Данный код можно использовать для кодирования 2–битовых двоичных чисел,

используя следующее (произвольное) соответствие:

Найдем кодовое расстояние этого кода:

;

;

;

;

;

.

Следовательно, для этого кода .

Замечание – характеризует корректирующую способность кода .

10 Вес Хэмминга вектора равен числу ненулевых позиций , обозначается . Например, .

Используя определение веса Хэмминга, получим очевидное выражение (1.1)

Пример – ;

.

Из выражения (1.1) следует, что минимальное расстояние Хэмминга равно , где ; ; .

Замечание – Для нахождения минимального расстояния линейного кода не обязательно сравнивать все возможные пары кодовых слов. Если и принадлежат линейному коду , то – также является кодовым словом кода . Такой код является аддитивной группой (определена операция сложения) и, следовательно, , где и , т.е. справедлива теорема.

Теорема 1. Минимальное расстояние линейного кода равно минимальному весу ненулевых кодовых слов.

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

2 Контроль ошибок

Кодовое слово можно представить в виде вектора с координатами в – мерном векторном пространстве. Например, для вектор находится в трёхмерном евклидовом пространстве, рисунок 1.2. Разрешенными для передачи выбраны вектора и .

X0

1 0 0 1 1 0

1 0 1 1 1 1

0 0 0 0 1 0 X1

0 0 1 0 1 1

X2

Рисунок 1.2

Рисунок дает наглядную алгебраическую интерпретацию понятия “мощность кода”:

а) кодовые слова полного кода определяют – мерное пространство, состоящее из последовательностей (– трехмерное пространство, состоящее при из 8 последовательностей полного кода);

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

Под воздействием помех происходит искажение отдельных разрядов слова. В результате разрешённые для передачи кодовые векторы переходят в другие векторы (с иными координатами) – запрещённые. Факт перехода разрешённого слова в запрещённое для передачи слово можно использовать для контроля за ошибками.

Возможна ситуация, когда разрешённый вектор переходит в другой разрешённый кодовый