Главная страница | Контакты | Случайная страница Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

Обнаружение и исправление ошибок

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

В безызбыточных равномерных кодах длины k все 2 ^k возможных кодовых комбинаций используются, то есть любой из 2 ^k кодовой комбинации сопоставляется какой-либо символ внешнего алфавита. Такие коды получили название первичных кодов. Ошибка любой кратности в какой-либо кодовой комбинации всегда приводит к ошибочному декодированию этой кодовой комбинации.

Для обеспечения помехоустойчивости кода вводят дополнительные разряды. Если, например, для кодирования всех символов внешнего алфавита достаточно иметь k -разрядный первичный код, то для обеспечения помехоустойчивости к разрядам первичного кода добавляется r избыточных разрядов. При этом длина результирующей кодовой комбинации становится равной n = k + r. Избыточные коды делятся на разделимые и неразделимые.

В разделимых кодах роль разрядов кодовой комбинации разграничена: часть разрядов, часто совпадающая с разрядами исходного первичного кода, являются информационными, остальные разряды играют роль проверочных разрядов. В неразделимых кодах все разряды равноправные, и в кодовой комбинации нельзя отделить информационные разряды от проверочных. Примером неразделимого кода может служить код с постоянным весом «3 из 7». Особенностью этого кода является то, что в любой его кодовой комбинации длины 7 имеется ровно три единицы. Обнаруживающая способность данного кода основывается на том, что любая одиночная ошибка изменяет количество единиц в кодовой комбинации.

Можно сказать, что помехоустойчивость достигается тем, что для кодирования используются не все кодовые комбинации, а только часть из них (для разделимых кодов эта часть равна 2 ^k). Остальные кодовые комбинации называются запрещёнными и при передаче информации не используются. Если d > 1, то любая одиночная ошибка будет переводить разрешённую комбинацию в запрещённую, наличие которой на принимающей стороне может служить индикатором ошибки.

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

Примером блочного разделимого кода может служить код с проверкой на чётность. Кодовая комбинация такого кода имеет вид a ₁ a ₂… a_k b. Первые k разрядов являются информационными, и, как правило, совпадают с разрядами исходного первичного кода. Последний разряд является избыточным и определяется как результат сложения по модулю 2 всех информационных разрядов. Если число единиц в информационных разрядах чётное, то b = 0, в противном случае b = 1. Такой код обеспечивает значение d = 2 и обладает способностью обнаруживать все ошибки кратности 1.

Для оценки качества кодов применяют коэффициент избыточности и коэффициент повышения верности. Коэффициент избыточности определяется выражением

где H _max – максимальная энтропия n -разрядного равномерного кода с числом кодовых комбинаций M = 2 ⁿ, при этом H _max = log₂ M = n. Под H (x) понимают максимальную энтропию разрешённых кодовых комбинаций, число которых обозначают через N, тогда H (X) = log N. Для неразделимого кода:

(13.2)

Например, для кода «3 из 7» максимальное количество кодовых комбинаций составляет 2⁷. Число разрешённых кодовых комбинаций . Тогда коэффициент избыточности равен:

Для разделимых кодов формула упрощается:

где n – длина кодовой комбинации, k – число информационных разрядов. Для n -разрядного кода с проверкой чётности получаем, что K_и = 1/ n.

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

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

Помехоустойчивые коды позволяют не только обнаруживать ошибки, но и исправлять их. Общая идея исправления ошибок кратности на более q_m заключается в следующем. Число возможных кодовых комбинаций M помехоустойчивого кода разбивается на N классов по числу разрешённых кодовых комбинаций. Разбиение осуществляется таким образом, чтобы в каждый класс входили одна разрешённая кодовая комбинация и ближайшие к ней запрещённые. При декодировании определяется, какому классу принадлежит принятая кодовая комбинация. Если кодовая комбинация принята с ошибкой, то есть является запрещённой, то она исправляется на разрешённую кодовую комбинацию, принадлежащую тому же классу.

Для обеспечения возможности исправления ошибок кратности не более q_m кодовое расстояние должно быть больше 2 q_m. Обычно оно выбирается по формуле d = 2 q_m +1. Актуальной является задача определения наибольшего числа N кодовых комбинаций n -разрядного двоичного кода с кодовым расстоянием d. В теории кодирования существуют следующие оценки:

Оценим корректирующий код, исправляющий одиночные ошибки (q_m =1) на основе 4-разрядного двоичного кода, общее число комбинаций которого равно 16. Среди этих 16 кодовых комбинаций нужно выбрать максимальное число разрешённых комбинаций, отстоящих друг от друга на расстояние не меньше, чем d = 2 q_m +1 = 3. Оценим верхнюю границу количества разрешённых кодовых комбинаций: N ≤ 2 ⁿ /(1+ n) = 3. На самом деле их нельзя найти больше двух.

13.3 Матричное представление (n, k)-кодов.

Среди блочных кодов широкое распространение получили линейные коды. Для определения линейного кода воспользуемся представлением кодовых комбинаций в виде элементов n -мерного векторного пространства V над полем P. Под полем P понимают символы выходного алфавита (внутреннего алфавита системы), число которых равно m. Линейными m -ичными кодами называются k -мерные подпространства n -мерного пространства V. При этом число n имеет смысл длины кодовой комбинации, число k определяет число информационных разрядов. Линейные коды называют также (n, k)-кодами.

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

Запишем кодовую комбинацию в виде a ₁ a ₂… a_kb ₁ b ₂… b_r. Первые k -разрядов являются информационными, остальные – проверочными. Проверочные символы кодовых комбинаций формируются из информационных символов на основе выражения

(13.3)

Здесь коэффициенты c_{j 1}, c_{j 2}, …, c_jk принимают значения из множества {0, 1}.

Любая кодовая комбинация, состоящая из k информационных разрядов, все проверочные разряды которой составлены в соответствие с формулой (13.3), является разрешённой комбинацией (n, k)-кода.

Пусть u и v – две разрешённые комбинации группового (n, k)-кода. Тогда кодовая комбинация w = u + v также является разрешённой комбинацией этого кода. Действительно, пусть

Тогда

,

где

Следовательно, проверочные разряды b_j'' кодовой комбинации w формируются в соответствии с выражением (13.3), поэтому кодовая комбинация w также является разрешённой.

Любые k линейно независимых векторов n -мерного линейного векторного пространства порождают k -мерное подпространство, образуя базис этого подпространства. Отсюда следует, что для задания (n, k)-кода достаточно выбрать k любых линейно независимых разрешённых кодовых комбинаций, а остальные разрешённые кодовые комбинации получать как линейные комбинации выбранных базисных векторов.

Обычно для задания (n, k)-кода пользуются этой возможностью, представляя k линейно независимых кодовых комбинаций в форме матрицы. Такая матрица называется порождающей матрицей (n, k)-кода. В общем виде её можно представить следующим образом:

(13.4)

Порождающая матрица G_{n , k} двоичного кода порождает ровно 2 ^k разрешённых кодовых комбинаций.

В зависимости от выбранного базиса k -мерного подпространства n -мерного кодового пространства кодовое расстояние совокупности 2 ^k векторов будет различным. При проектировании (n, k) кода ставится задача оптимального размещения кодовых векторов в n -мерном кодовом пространстве в соответствии с заданной статистикой ошибок и, в частности, обеспечения максимально возможного кодового расстояния.

Пусть v ₁, v ₂, …, v _k – кодовые векторы-строки, составляющие порождающую матрицу

Тогда разрешённую кодовую комбинацию (n, k)-кода можно представить в виде линейной комбинации векторов

(13.5)

где g ₁, g ₂, …, g_k – коэффициенты, принимающие значения из множества {0, 1}.

Проверочные разряды b ₁, …, b_r кодового вектора v, передаваемого по каналу связи, формируются в соответствии с (13.3). Это же соотношение может быть использовано на приёмном конце канала для проверки правильности кодовой комбинации: равенство (13.3) должно выполняться, если ошибки не произошло. С каждой принятой кодовой комбинацией можно связать систему проверок по числу проверочных разрядов, которая может быть описана следующей системой уравнений:

(13.6)

Здесь . Нули в правых частях равенств истолковываются как отсутствие ошибки в принятой кодовой комбинации v. Для удобства систему проверок (13.6) записывают в матричной форме, а именно как произведение вектор-строки v, соответствующей принятой кодовой комбинации, на матрицу проверочных коэффициентов:

Матрицу H_{n , k} называют проверочной матрицей. Система проверок (13.6) может быть записана в виде:

(13.7)

В общем случае результат умножения может быть отличен от нуля

где

Вектор-строка называется синдромом ошибки. Всего может быть 2 ^r –1 различных ненулевых синдромов, разбивающих множество возможных ошибок на 2 ^r –1 класса. Это позволяет по виду синдрома ошибки определять, к какому классу относится ошибка. Часто (n, k)-код проектируется таким образом, что с вероятностью, близкой к единице, каждый из выделенных 2 ^r –1 классов ошибок содержит всего по одному элементу. Такие коды позволяют исправлять ошибки.

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

Если к какой-либо строке v_i порождающей матрицы G_{n , k} прибавить линейную комбинацию других строк, то от этого порождающая матрица не изменится в том смысле, что останется порождающей матрицей того же самого (n, k)-кода. Путём такой замены строк матрицу G_{n , k} можно привести к каноническому виду:

(13.8)

канонический вид порождающей матрицы удобен тем, что существует простая связь между элементами порождающей и проверочной матриц: для определения проверочной матрицы (n, k)-кода, порождаемого матрицей вида (13.8), нужно транспонировать подматрицу проверочных разрядов матрицы G_{n , k} и приписать справа к полученной матрице единичную матрицу размерности . Следовательно, матрице (13.8) соответствует проверочная матрица: