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

 

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

РЕФЕРАТ

На тему:

 

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

МИНСК, 2008

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

 

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

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

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

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

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

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

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

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

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

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

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

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

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

1)  свёрточные;

2)  цепные;

3)  непрерывные.

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

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

На рисунке 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)

Пример – ;

3

 .

Из выражения (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.        Пусть ; ; код  задан векторами  и .

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

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

mod 2

.

mod 2

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

==

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

                               =

=                                .  

                               =

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

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

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

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

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

,

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

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

ЛИТЕРАТУРА

 

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

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

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

БЕЛОРУССКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИНФОРМАТИКИ И РАДИОЭЛЕКТРОНИКИ Кафедра радиотехнических системРЕФЕРАТ На тему: «Параметры кодов. Контроль, обнаружение и исправление ошибок»МИНСК, 2008 1. Параметры кодов

 

• 14:21 05 Июля 2016
  Российско-китайский медуниверситет откроет магистерскую программу по TCM
• 01:21 05 Июля 2016
  На форуме МГУ Россия и Китай обсудят научно-образовательное сотрудничество
• 11:00 04 Июля 2016
  Реморенко: "ЕГЭ-туризм" в России сходит на нет
• 10:52 04 Июля 2016
  Летняя российско-австрийская школа откроется в Москве
• 15:31 01 Июля 2016
  В СПбГУ могут воссоздать географический факультет

Заказать уникальную работу