Симметричный двоичный канал

Канал, в котором вероятности ложного опознавания символов Р_0–1, и Р_1–0 одинаковы по величине. В противном случае канал называется асимметричным.

Канал с независимыми (некоррелированными) ошибками

Канал, в котором вероятность ошибки в опознавании символа на данном такте не зависит от наличия ошибок на предшествующем. Наличие/отсутствие ошибки на данном такте не влияет на вероятность аналогичного события на последующем.

Для двоичного канала это означает, что вероятности Р_0–1 = Сonst₁; Р_1–0 = Сonst₂, т.е. не зависят от времени, порядка следования символов в кодовом слове.

Код

1. В широком смысле - соглашение между отправителем и получателем сообщений о правилах формирования и интерпретации сигналов.

2. В узком смысле - совокупность символов алфавита и система определенных правил, при помощи которых информация может быть представлена (закодирована) в виде набора из таких символов для передачи, обработки и хранения. Конечная последовательность символов называется кодовым словом [4].

Равномерный код

Код, все слова которого имеют одинаковую длину. В противном случае код называется неравномерным.

Префиксный код

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

Кодовый вектор

Одна из возможных математических интерпретаций кодового слова, при которой каждый элемент слова рассматривается как независимая координата, принимающая значения из конечного дискретного множества, называемого алфавитом. Двоичный вектор образует двоичные векторы. Слово длины n интерпретируется как n - мерный вектор.

Вес двоичного вектора w(V_i)

Это число единиц, содержащихся в векторе. Здесь V_i – это вектор, принадлежащий коду.

Двоичный вектор ошибки Еj

Вектор, расположение единиц в котором соответствует расположению искаженных элементов в векторе F_i. Математическая модель происхождения ошибок F_i=V_i Å E_j, где Å - знак суммирования по mod2, V_i - неискаженный вектор.

Расстояние (Хэмминга) между двумя двоичными векторами

1) минимальное число ребер геометрической модели векторного пространства, соединяющих данные векторы;

2) вес суммы по mod2 рассматриваемых векторов d_i,j = w(A _i Å A _j).

Минимальное расстояние двоичного кода d₀

Минимальное значение из всех попарных расстояний между векторами кода.

Неизбыточный двоичный код (на все сочетания)

Код с минимальным расстоянием d₀ = 1.

Избыточный двоичный код

Код с расстоянием d₀ > 2.

Разделимый избыточный код

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

Систематический разделимый код

Код, в словах которого все контрольные символы расположены компактной группой (обычно в конце слова).

Относительная скорость R избыточного (n,k)-кода

Показатель снижения скорости передачи сообщений относительно неизбыточного кода R=k/n.

Синдром

1). (Медицина). Закономерное сочетание симптомов, обусловленное единым патогенезом [4] (от греческого syndrome - скопление).

2). (Кодирование). Вектор S = F_i*H^Т= Е _j*Н^Т длины (n-k), рассматриваемый как признак наличия ошибок в кодовом слове.

Здесь F_i - декодируемое слово (n,k)-кода;

Н^Т - транспонированная проверочная матрица;

E _j - вектор ошибок, который «породил» данный синдром.

Декодирование по синдрому

1. Декодирование с обнаружением ошибок (без попытки исправлять) - отнесение принятого слова (n,k)-кода к категории «разрешенных», отображающих сообщения, если синдром S=0, предъявление слова получателю. Отнесение к категории «запрещенных», если S≠0, «стирание» принятого слова.

2. Декодирование с исправлением ошибок - вычисление (или выборка из памяти) вектора ошибки Е _j по найденному синдрому. Предъявление получателю слова Q _i = F_i Å E _j, где F_i принятое из канала слово (n,k)-кода. Не исключается Е = 0. Тогда Q _i = F_i = V_i.

БИБЛИОГРАФИЧЕСКИЙ СПИСОК

 

1. Дмитриев В.И. Прикладная теория информации: Учебник для студентов вузов по спец. «Автоматизированные системы обработки информации и управления». М.: Высшая школа, 1989. 320 с.

2. Гойхман Э.Ш., Лосев Ю.И. Передача информации в АСУ. М.:Связь, 1976. 280 с.

3. Аршинов М.Н., Садовский Л.Е. Коды и математика. М.:Наука, Главная редакция физико-математической литературы, 1983. 144 с.

4. Энциклопедический словарь / Гл. ред. А.М. Прохоров. 3-е изд. М.:Сов. энциклопедия, 1984. 1600 с.