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