Навигация
1.1.2 Представление кодов
Для построения кодов используются методы теории чисел, алгебры, комбинаторики, теории вероятности и т.д. Коды могут быть представлены в виде формул, таблиц, графов, геометрически и т.д.
Кодовые комбинации можно представить в виде полиномов.
Любое число в любой системе счисления с основанием x может быть представлено в виде суммы ряда. Для целых чисел эта сумма имеет вид:
,(2)
где x – основание системы счисления, a – символ системы счисления, i – показатель степени основания системы счисления и индекс позиции i-го члена ряда.
Иначе коды представляются в виде матриц. Равномерные n‑значные x‑е коды можно представить в виде матрицы, содержащей xn строк и n столбцов. Если исключить нулевые комбинации кода, то число строк будет равно xn – 1.
Особенностью такого способа представления кода является то, что комбинация кода, полученная в результате сложения произвольно взятых строк матрицы также является одной из комбинаций данного кода т.к. в матрице записаны все xn – 1 кодовые комбинации n‑значного кода.
Если суммировать строки матрицы по mod x, то можно получить нулевую строку. После её исключения получится новая матрица с меньшим числом строк, в которой тоже можно определить нулевую строку и исключить её и т.д. до тех пор пока строки станут линейно независимы, т.е. сложение по mod x не даёт нулевой строки. Полученная в результате матрица будет диагональной и единичной т.е. главная диагональ матрицы состоит из единиц, а остальные равны 0. Умножение произвольной матрицы на диагональную единичную не меняет её значений. Если строки этой матрицы складывать по mod x, то можно восстановить все комбинации n‑значного кода. Поэтому такие матрицы называют образующими или определяющими. Определяющая матрица называется транспонированной, если главная диагональ слева вверх направо.
1.1.3 Классификация кодов
Всё множество известных в настоящее время кодов условно делят на два направления: непомехозащищённые и помехозащищённые.
К первому направлению относятся следующие коды:
Двоичный код на все сочетания – кодовые комбинации этого кода соответствуют записи натурального ряда чисел в двоичной системе счисления. Общее число комбинаций этого кода равно
N = 2n ,
где N – общее число комбинаций кода; n – длина кода.
Единично‑десятичный код. Каждому разряду десятичного числа соответствует определённое количество единиц. Разряды отделяются интервалами. Этот код неравномерный, но может быть преобразован в равномерный, если слева в каждом разряде дописать недостающие единицы нулями до 10 знаков.
Двоично‑десятичный код. Каждый разряд десятичного числа записывается в виде комбинации кодов. Существует несколько видов двоично‑десятичных кодов: код с весовыми коэффициентами 8.4.2.1, код с весовыми кэффициентами 2.4.2.1 (код Айкена)
Число‑импульсный код – единичный (унитарный), кодовые комбинации различаются числом единиц.
Код Морзе – относится к неравномерным кодам. Кодовые комбинации имеют разную длительность: точка – 1, тире – 111, интервал между точкой и тире – 0, интервал между комбинациями (буквами) – 000.
Код Бордо – равномерный пятиэлементный телеграфный код. Максимальное число комбинаций N = 25 = 32.
Код Грея (рефлексивный, отражённый). Две соседние комбинации отличаются только в соседних разрядах: Для преобразования обычного двоичного кода в код Грея необходимо сложить данную комбинацию с самой по mod 2, но сдвинутой вправо на один разряд.
Помехозащищённые (помехоустойчивые или корректирующие) коды предназначены для обнаружения и исправления ошибок. В теореме К. Шеннона утверждается, что вероятность ошибок для дискретного канала с помехами может быть сведена к минимуму с помощью выбора соответствующего способа кодирования. В двоичных кодах каждый разряд может принимать значения 0 или 1. Количество единиц в кодовой комбинации называют весом кодовой комбинации и обозначают w. Например, кодовая комбинация 100101100 имеет длину (значность) 9 и вес w = 4. Степень отличия двух кодовых комбинаций называется кодовым расстоянием или расстоянием Хемминга, оно обозначается как d. Кодовое расстояние – это минимальное расстояние между кодовыми комбинациями, определяемое количеством (числом) отличающихся позиций или символов в кодовых комбинациях. Для вычисления кодовых расстояний используется сложение по mod 2.
При воздействии помех в кодовой комбинации в одном или нескольких разрядах возможна трансформация 0 в 1 и 1 в 0 и получается наложенная комбинация. Ошибки, полученные в разряде кодовой комбинации, называют однократными. При 2‑х, 3‑х и т.д. разрядах – двукратными, трёхкратными и т.д.
Для определения мест ошибок в кодовой комбинации вводится понятие вектора ошибок. Вектор ошибок n‑разрядного кода – это n‑разрядная комбинация, единицы в которой указывают положение искажённых символов кодовой комбинации.
Вес вектора ошибки we характеризует кратность ошибки. Сумма по модулю 2 для искажённой кодовой комбинации и вектора ошибки равна исходной неискажённой комбинации.
Помехоустойчивость кодирования обеспечивается за счёт введения избыточности в кодовые комбинации. Это значит, что не все n символов кодовой комбинации используются для кодирования информации, а только какая их часть k<n. Следовательно, из всех возможных комбинаций N0 = 2n для кодирования используется Nk = 2k комбинаций, т.е. всё множество возможных кодовых комбинаций делится на две группы:
Группа Nk = 2k – разрешённых комбинаций.
Группа (N0 – Nk) = 2n – 2k – запрещённых комбинаций.
Если на приёмной стороне получена разрешённая комбинация, то считается, что искажений нет, иначе принятая комбинация искажена.
В общем случае каждая из Nk разрешённых комбинаций может трансформироваться в любую из N0 возможных комбинаций, т.е. всех возможных комбинаций может быть Nk*N0, Nk(Nk–1) переходы одних разрешённых комбинаций в другие разрешённые и Nk(N0–Nk) переходов в запрещённые комбинации.
Таким образом, не все искажения могут быть обнаружены, а только те, для которых определяются следующим уравнением:
.(3)
Для построения кода, обеспечивающего не только обнаружения ошибок, но и исправление ошибок. Множество запрещённых кодовых комбинаций разбивается на Nk непересекающихся подмножеств Nk, каждому из которых ставится в соответствие одна из разрешённых комбинаций. В этом случае, если принятая запрещённая комбинация принадлежит подмножеству Mi, то считается, что передана комбинация Аi и ошибка будет исправлена. Т.о. ошибка исправляется в (N0-Nk) случаях, равных количеству запрещённых комбинаций от общего числа обнаруженных ошибочных комбинаций определяется уравнением:
.(4)
Выбор способа разбиения на подмножества определяется типом ошибок. Допустим, необходимо построить код, обнаруживающий все ошибки кратностью t и меньше. Это значит, что из множества всех возможных комбинаций N0 необходимо выбрать Nk разрешённых комбинаций так, чтобы любая из них в сумме по модулю два с любым вектором ошибок E с весом we£t не была равна никакой другой разрешённой комбинации. Для этого необходимо, чтобы кодовое расстояние удовлетворяло равенству:
dmin ³ t + 1, (5)
где dmin – наименьшее расстояние Хэмминга.
Похожие работы
... взаимной нестабильности несущей частоты излучаемого сигнала и частоты настройки приемника и доплеровского сдвига. 2.2 Расчет энергетических характеристик Качество выделения информации приемным устройством цифровой системы передачи информации, связано с вероятностью ошибки приёма разряда сообщения. Связь между допустимым значением вероятности ошибки Рд и пороговым отношением мощности сигнала к ...
... сигналу дорівнює добутку ширини спектра сигналу на його тривалість і визначається [9] (1.6.1), де B – база сигналу. 2. Аналіз відомих технічних рішень побудови радіоприймального пристрою цифрової системи передачі інформації Структурна схема приймача в значній мірі визначається його призначенням, і видом модуляції сигналу. В структурному відношенні всі існуючі приймачі можна розділити на ...
... универсальный сервер часто называют сервером приложений. Серверы в сети часто специализируются. Специализированные серверы используются для устранения наиболее "узких" мест в работе сети: создание и управление базами данных и архивами данных, поддержка многоадресной факсимильной связи и электронной почты, управление многопользовательскими терминалами (принтеры, плоттеры) и др. Файл-сервер (File ...
... 1.5 Уровни помех и линейных затуханий 1.5.1 Электрические помехи в каналах ВЧ связи по ВЛ Электрические помехи имеются в любом канале связи. Они являются основным фактором, ограничивающим дальность передачи информации из-за того, что сигналы, принимаемые приемником, искажаются помехами. Для того чтобы искажения не выходили за пределы, допустимые для данного вида информации, должно быть ...
0 комментариев