Радиотехническая система передач
БЕЛОРУССКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИНФОРМАТИКИ И РАДИОЭЛЕКТРОНИКИ
Кафедра радиотехнических систем
РЕФЕРАТ
На тему:
«Параметры кодов. Контроль, обнаружение и исправление ошибок»
МИНСК, 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 последовательностей
полного кода);
б) кодовые
слова избыточного
кода определяют
подпространство
(подмножество)
– мерного
пространства,
состоящее из
последовательностей.
Под воздействием помех происходит искажение отдельных разрядов слова. В результате разрешённые для передачи кодовые векторы переходят в другие векторы (с иными координатами) – запрещённые. Факт перехода разрешённого слова в запрещённое для передачи слово можно использовать для контроля за ошибками.
Возможна ситуация, когда разрешённый вектор переходит в другой разрешённый кодовый