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

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

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

РЕФЕРАТ

На тему:

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

МИНСК, 2008

1. Параметры кодов

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

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

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

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

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

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

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

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

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

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

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

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

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

свёрточные;

цепные;

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

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

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

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

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

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

Блоковый код

k₀ битов/кадр n₀ битов/кадр n₀ битов/кадр k₀ битов/кадр

Непрерывный код Рисунок 1.1

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

;;; .

Данный код можно использовать для кодирования 2-битовых двоичных чисел, используя следующее (произвольное) соответствие:

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

;

;

;

;

;

.

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

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

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

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

Пример — ;

.

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

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

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

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

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

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

X₀

1 0 0 1 1 0

1 0 1 1 1 1

0 0 0 0 1 0 X₁

0 0 1 0 1 1

X₂

Рисунок 1.2

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

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

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

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

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

Из рассмотренной модели можно сделать следующий важный вывод: для

того чтобы передаваемые векторы можно было бы отличать друг от друга при наличии помех, необходимо располагать эти векторы в — мерном пространстве

как можно дальше друг от друга. Из этой же — мерной модели следует геометрическая интерпретация расстояния Хэмминга: — это число рёбер, которые нужно пройти, чтобы перевести один вектор в другой, т. е. попасть из вершины одного вектора в вершину другого.

2.1 Обнаружение и исправление ошибок

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

Пример 1. Пусть;. Разрешенным для передачи является множество кодовых слов:

.

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

Пример 2. Пусть теперь подмножество разрешённых кодовых слов предоставлено в виде двоичных комбинаций с чётным числом единиц.

.

Заданный код имеет. Запрещенные кодовые слова представлены в виде подмножества :

.

Если, то ни одно из разрешенных кодовых слов (т.е. кода) при одиночной ошибке не переходит в другое разрешённое слово этого же кода. Таким образом, код обнаруживает:

— одиночные ошибки;

— ошибки нечетной кратности (для — тройные).

Например, тройная ошибка кодового слова; , переводит его в запрещенный вектор .

Вывод — В общем случае, при необходимости обнаруживать ошибки кратности кодовое расстояние кода должно быть

.

Пример 3. Пусть;; код задан векторами и .

При возникновении одиночных ошибок или множества векторов

кодовому слову соответствует следующее запрещенное подмножество

.

Кодовому слову соответствует запрещенное подмножество

==

Таким образом, коду — разрешенному для передачи подмножеств векторов соответствует два запрещенных подмножества векторов и :

=

= .

=

Стратегия исправления ошибок заключается в следующем:

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

— структура кодового запрещенного подмножества, относящаяся к соответствующему исходному разрешенному подмножеству, позволяет определить местоположение ошибки, т. е. исправить ошибку.

Для исправления ошибок кратности кодовое расстояние должно удовлетворять соотношению. (1.2)

Используя эту формулу, можно записать

где обозначает целую часть числа .

Замечание — Существуют модели каналов (например, канал с дефектами), в которых величина может быть больше, чем в выражении (1.2).

· Митюхин А. И., Игнатович В. Г. Линейные групповые коды: Учеб. пособие. — Мн. :БГУИР, 2002.

· Митюхин А. И. Элементы абстрактной алгебры: Учеб.пособие. — Мн.: БГУИР, 2000.

· Лосев В. В. Помехоустойчивое кодирование в радиотехнических системах передачи информации: Метод. Пособие Ч.1. Линейные коды. — Мн.: ВШ, 2004.