Основные понятия и определения теории информации и кодирования. Задачи теории информации и кодирования, страница 10

Б Л О К О В Ы Е  К О Д Ы

Блоковые коды называются обычно (n,k) - кодами,где n - количество разрядов в кодовой комбинации(принято называть ДЛИНОЙ или ЗНАЧНОСТЬЮ КОДА), k - количество информационных разрядов.

Мы будем рассматривать только двоичные помехоустойчивые коды.Двоичный код - код с основанием m = 2.

Символы каждого разряда кодовой комбинации могут принимать значения 0 или 1.Количество единиц в кодовой комбинации называют ВЕСОМ

КОДОВОЙ КОМБИНАЦИИ и обозначают w.

НАПРИМЕР,кодовая комбинация 1001001 характеризуется значностью

n = 7 и весом w = 3.

РАССТОЯНИЕ по ХЭММИНГУ характеризует степень отличия любых двух кодовых комбинаций и обозначается d.Оно выражается числом позиций или символов,в которых комбинации отличаются одна от другой,и определяется какВЕС СУММЫ ПО МОДУЛЮ ДВА этих КОДОВЫХ КОМБИНАЦИЙ.

НАПРИМЕР,для определения расстояния между комбинациями 10010010 и

11011000 нужно просуммировать их по модулю два.

10010010

+

11011000

──────────

01001010

Вес полученной комбинации w = 3,поэтому расстояние между исходными комбинациями равно d = 3.

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

Если ОШИБКИ происходят только в одном разрядекодовой комбинации,то их называют ОДИНОЧНЫМИ (однократными).При наличии ошибок в двух,трёх и т.д.разрядах ошибки называют ДВУХКРАТНЫМИ,ТРЁХКРАТНЫМИ и т.д.

Для указания мест в кодовой комбинации,где имеются искажения символов,используется вектор ошибки e.ВЕКТОР ОШИБКИ n - разрядного кода

- это n - разрядная комбинация,единицы в которой указывают положение искажённых символов кодовой комбинации.

НАПРИМЕР,если для пятиразрядного ода вектор ошибки имеет вид e =

01100,то это значит,что имеют место ошибки во втором и третьем разрядах кодовой комбинации.

Вес вектора ошибки We определяет кратность ошибки.Сумма по модулю два искажённой кодовой комбинации и вектора ошибки даёт исходную неискажённую комбинацию.

Помехоустойчивость кодирования обеспечивается  за счёт введения

ИЗБЫТОЧНОСТИ в кодовые комбинации.Это значит,что из n символов кодовой комбинации для передачи информации используется k < n символов.Следовательно,из общего числа N0 = 2^n возможных кодовых комбинаций для передачи информации используется только N = 2^k

комбинаций.В соответствии с этим всё множество N0 = 2^n возможных кодовых комбинаций делится на два подмножества:в первое входит множество N = 2^k разрешённых комбинаций,во второе - множество N0 - N

запрещённых комбинаций.

Способ разбиения на подмножества зависит от того,какие ошибки должны исправляться данным кодом.

С В Я З Ь   К О Р Р Е К Т И Р У Ю Щ Е Й   С П О С О Б Н О С Т И

К О Д А   С   К О Д О В Ы М   Р А С С Т О Я Н И Е М .

НАИМЕНЬШЕЕ РАССТОЯНИЕ ПО ХЭММИНГУ между разрешёнными кодовыми комбинациями d min - очень важная характеристика кода,ибо именно она

ХАРАКТЕРИЗУЕТ его КОРРЕКТИРУЮЩИЕ СПОСОБНОСТИ.

Рассмотрим это на примерах.

Пусть необходимо построить КОД,ОБНАРУЖИВАЮЩИЙ все ОШИБКИ КРАТНОСТЬЮ

t и ниже.

Построить такой код - это значит из множества N0 возможных выбрать

N разрешённых комбинаций так,чтобы любая из них в сумме по модулю два с любым вектором ошибок с весом We < = t не дала бы в резуьтате никакой другой разрешённой комбинации.Для этого необходимо,чтобы наименьшее кодовое расстояние удовлетворяло условию

d min > = t + 1 .

ПРИМЕР.Рассмотрим код со значностью n = 3. Все возможные комбинации такого кода имеют вид:

A1    A2    A3    A4    A5    A6    A7    A8

000   001   010   011   100   101   110   111

Для того,чтобы код обеспечивал обнаружение однократных ошибок,необходимо из всего множества N0 = 8 возможных комбинаций выбрать в качестве разрешённых такие,расстояние между которыми было бы не менее

d = 2.Вкачестве примера разрешённых комбинаций в этом случае можно выбрать:

A1 = 000;    A4 = 011;     A6 = 101;     A7 = 110.

Для обнаружения двукратных ошибок d min = 3.При этом в качестве примера разрешённых комбинаций можно выбрать: