Пред.
След.
Макеты страниц
Распознанный текст, спецсимволы и формулы могут содержать ошибки, поэтому с корректным вариантом рекомендуем ознакомиться на отсканированных изображениях учебника выше Также, советуем воспользоваться поиском по сайту, мы уверены, что вы сможете найти больше информации по нужной Вам тематике ДЛЯ СТУДЕНТОВ И ШКОЛЬНИКОВ ЕСТЬ
ZADANIA.TO
3.4. Методы исправления ошибокСуществует два основных метода исправления ошибок. Первый метод основан на использовании кодов-спутников. В этом случае строится кодовая таблица, в первой строке которой располагаются все кодовые слова Вес вектора Таблица 16 (см. скан) Все коды-спутники рабочих кодовых комбинаций хранятся в памяти машины, и в случае приема комбинации, совпадающей с одним из кодов спутников, искаженная комбинация расшифровывается как исходная рабочая комбинация, в которую входит данный код-спутник. Пример. Определить коды-спутники для кода, исправляющего одиночную ошибку со следующими четырьмя рабочими комбинациями: 01001, 01110, 10010, 10101. Поскольку
Благодаря кодам-спутникам принятая, например, искаженная комбинация 10111 расшифруется как исходная! 10101. Такой метод исправления ошибок требует большого объема оборудования, особенно при длинных кодовых комбинациях, так как число запоминающих ячеек становится чрезвычайно большим. Поэтому на практике применяется другой метод исправления ошибок, при котором используются проверочные соотношения, записанные на основании проверочной матрицы Я. При этом проверка кодовой комбинации на приеме выполняется путем сопоставления принимаемых проверочных разрядов кодовой комбинации и проверочных разрядов, вычисленных на основании принятых информационных. Их сумма по модулю два называется синдромом. Характерная особенность синдрома то, что он не зависит от вида переданной комбинации, а полностью определяется ошибками, поразившими принятую комбинацию. Между комбинацией синдрома и вызвавшей его комбинацией ошибки нет взаимного однозначного соответствия — одному и тому же синдрому соответствует 2 различных комбинаций ошибок. Так, нулевому синдрому соответствует нулевая комбинация ошибок, а также соответствующих нулевому синдрому, может быть исправлена кодом. При этом за каждым синдромом закрепляется такая исправляемая комбинация ошибок, появление которой в канале наиболее вероятно. Поскольку синдром — сумма по модулю два проверочных разрядов кодовой комбинации и проверочных разрядов, вычисленных по принятым информационным символам, то, следовательно, он совпадает с комбинацией результатов проверки на четность, определяемых проверочной матрицей Я. Если проверочный символ, вычисленный по информационным, обозначить
Таким образом, определяем синдром путем решения уравнений
Если код используется для исправления ошибок, то при декодировании должно быть заранее определено соответствие между видом синдрома и видом исправляемой ошибки. Установим это соответствие. Пусть ошибка воздействует в первом разряде (комбинация ошибки 1000000). Применим этой комбинации проверки (3.16):
Это значит, что при действии ошибки в первом разряде синдром равен Пусть, например, в кодовой комбинации 1101001 при передаче произошла ошибка во втором разряде и на вход декодирующего устройства поступила комбинация 1001001. При декодировании в соответствии с (3.16) будут получены следующие результаты: 1-я проверка Таблица 17 (см. скан) Таким образом, синдром равен 101. Это свидетельствует о том (табл. 17), что ошибочен именно второй разряд принятой комбинации. Из табл. 17 видно, что для указания ошибок могут использоваться все комбинации двоичного кода, кроме нулевой. Поэтому число разрядов синдрома, а следовательно, и число проверочных символов при исправлении однократных ошибок определяется неравенством
Для исправления не только единичных, но и двойных ошибок необходимо выполнение условия
В общем случае исправления одиночной ошибки довольно просто получить синдромы, позволяющие однозначно определить место ошибки в комбинации, то для исправления двойных, тройных и т. д. ошибок, а также для исправления пачек ошибок построение синдромов довольно затруднительно. До сих пор не имеется в литературе метода, который позволил бы построить систематический код для исправления множества ошибок. В работах [7, 76] разработан метод построения синдромов для кодов, предназначенных для исправления двойных, тройных, а также пачек ошибок длины Таблица 18 (см. скан) Таблица 19 (см. скан) В табл. 20 представлены синдромы Таблица 20 (см. скан) Ввиду сложности построения синдромов для исправления множества ошибок обычно процесс построения поручают вычислительным машинам. С помощью вычислительной машины Банерджи построил таблицу кодов для исправления любых двукратных ошибок в кодовых комбинациях длиной до 29 разрядов (приложение 1). В первой графе этой таблицы указан тип кода. Каждая из остальных граф соответствует одному из проверочных разрядов комбинации. Чтобы определить значение проверочного символа (0 или 1) в любом из этих разрядов, нужно сложить по модулю два информационный сим
|
1 |
Оглавление
|