Коды обнаруживающие и исправляющие ошибки урок план

Линейные является кодовым словом, то его циклическая перестановка также является кодовым словом.

Слова циклического кода удобно представлять в виде многочленов. Например, кодовое слово >=(v_,\;v_,\;\ldots ,\;v_)>" width="" height="" />
представляется в виде полинома +v_x+\ldots +v_x^>" width="" height="" />
. При этом циклический сдвиг кодового слова эквивалентен умножению многочлена на " width="" height="" />
по модулю -1>" width="" height="" />
.

могут принимать значения 0 или 1.

Порождающий (генераторный) полином

. Порождающий полином является делителем -1>" width="" height="" />
.

С помощью порождающего полинома осуществляется кодирование циклическим кодом. В частности:

Коды CRC

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

задаёт конкретный код CRC. Примеры наиболее популярных полиномов:

название кода	степень	полином
CRC-12	12
CRC-16	16
CRC- CCITT	16
CRC-32	32

Коды БЧХ

Коды Боуза — Чоудхури — Хоквингема (БЧХ) являются подклассом циклических кодов. Их отличительное свойство — возможность построения кода БЧХ с минимальным расстоянием не меньше заданного. Это важно, потому что, вообще говоря, определение минимального расстояния кода есть очень сложная задача.

на множители в Коды коррекции ошибок Рида — Соломона

Преимущества и недостатки блоковых кодов

Хотя блоковые коды, как правило, хорошо справляются с редкими, но большими пачками ошибок, их эффективность при частых, но небольших ошибках (например, в канале с Свёрточные коды

)

Преимущества и недостатки свёрточных кодов

Свёрточные коды эффективно работают в канале с белым шумом, но плохо справляются с пакетами ошибок. Более того, если декодер ошибается, на его выходе всегда возникает пакет ошибок.

Каскадное кодирование. Итеративное декодирование

Преимущества разных способов кодирования можно объединить, применив каскадное кодирование. При этом информация сначала кодируется одним кодом, а затем другим, в результате получается код-произведение.

Например, популярной является следующая конструкция: данные кодируются кодом Рида-Соломона, затем перемежаются (при этом символы, расположенные близко, помещаются далеко друг от друга) и кодируются свёрточным кодом. На приёмнике сначала декодируется свёрточный код, затем осуществляется обратное перемежение (при этом пачки ошибок на выходе свёрточного декодера попадают в разные кодовые слова кода Рида — Соломона), и затем осуществляется декодирование кода Рида — Соломона.

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

Оценка эффективности кодов

. Тогда справедливо неравенство (называемое границей Хемминга):

Коды, удовлетворяющие этой границе с равенством, называются совершенными. К совершенным кодам относятся, например, Энергетический выигрыш

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

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

Применение кодов, исправляющих ошибки

Коды, исправляющие ошибки, применяются:

в системах Автоматический запрос повторной передачи

Системы с автоматическим запросом повторной передачи (ARQ — Automatic Repeat reQuest) основаны на технологии обнаружения ошибок. Распространены следующие методы автоматического запроса:

Запрос ARQ с остановками (stop-and-wait ARQ)

Идея этого метода заключается в том, что передатчик ожидает от приемника подтверждения успешного приема предыдущего блока данных перед тем как начать передачу следующего. В случае, если блок данных был принят с ошибкой, приемник передает отрицательное подтверждение (negative acknowledgement, NAK), и передатчик повторяет передачу блока. Данный метод подходит для Непрерывный запрос ARQ с возвратом (continuous ARQ with pullback)

Для этого метода необходим Непрерывный запрос ARQ с выборочным повторением (continuous ARQ with selective repeat)

При этом подходе осуществляется передача только ошибочно принятых блоков данных.

См. также

• Линейный код
• Код Боуза — Чоудхури — Хоквингема
• Литература

• Мак-Вильямс Ф. Дж., Слоэн Н. Дж. А. Теория кодов, исправляющих ошибки. М.: Радио и связь, 1979.
• Блейхут Р. Теория и практика кодов, контролирующих ошибки. М.: Мир, 1986.
• Морелос-Сарагоса Р. Искусство помехоустойчивого кодирования. Методы, алгоритмы, применение. М.: Техносфера, 2005. — ISBN 5-94836-035-0

Ссылки

Имеется Помехоустойчивое кодирование ( раздела Википедии на русском языке. Оригинальная статья находится по адресу: Обнаружение и исправление ошибок. Список первоначальных авторов статьи можно посмотреть в истории правок. Эта статья так же, как и статья, размещённая в Википедии, доступна на условиях CC-BY-SA .

В статье размещена информация о кодировании с исправлением ошибок, в конце представлено домашнее задание. Материал актуален для подготовки к ЕГЭ.

Введение

Ключевые слова:

00101 0011010101 1001001010011

Как вы рассуждали?

1000 0110 1011101011 11111111

Применение бита чётности позволяет обнаруживать нечётное число ошибок (1, 3, 5, . ), а ошибки в чётном количестве разрядов остаются незамеченными.

При передаче больших файлов может сразу возникнуть множество ошибок, поэтому используют другой метод — вычисляют контрольную сумму файла (по достаточно сложным алгоритмам), которая передаётся вместе с данными. Изменение даже одного бита данных сильно изменяет контрольную сумму. Если контрольная сумма файла, вычисленная приёмником, не совпадает с контрольной суммой, записанной передающей стороной, то произошла ошибка.

Коды с исправлением ошибок

Когда вы говорите по телефону, иногда приходится повторять какието фразы, если собеседник не понял вас из-за помех. Эту идею можно использовать и для компьютеров, например применить код, в котором каждый бит повторяется трижды: вместо каждого нуля будем передавать кодовое слово 000, а вместо каждой единицы — кодовое слово 111.

Как вы рассуждали?

При передаче каждой тройки одинаковых битов произошло не более одной ошибки. Какие биты пытались передать, если получены тройки битов:

001 010 011 100 101 110?

Как вы рассуждали?

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

Помехоустойчивый код — это код, который позволяет исправлять ошибки, если их количество не превышает некоторого уровня.

Попробуйте придумать другой трёхбитовый код (содержащий два кодовых слова), который позволяет исправлять одну ошибку и обнаруживать одну или две ошибки. Что общего в коде с утроением битов и в вашем коде?

Рис. 2.9

Для передачи данных использовался код, заданный на рис. 2.9. Принята цепочка 00110. Определите букву, код которой отличается от этой цепочки меньше всего.

Для передачи данных использовался код, заданный на рис. 2.9. Принята цепочка 10101. Определите знаки, коды которых отличаются от этой цепочки меньше всего.

В каком случае при использовании кода, заданного на рис. 2.9:

Выводы

Интеллект-карта

Рис. 2.10

Домашнее задание

На сегодняшний день в мире передается огромное количество информации, хотя системы передачи данных отвечают всем требованиям. Они не являются столь совершенными.

Предварительный просмотр:

Федеральное государственное бюджетное образовательное учреждение

Факультет математики, информатики, физики и технологии

Кафедра прикладной информатики и математики

Направление: педагогическое образование

Профиль: Информатика и Технология

Дисциплина: Теоретические основы информатики

На сегодняшний день в мире передается огромное количество информации, хотя системы передачи данных отвечают всем требованиям. Они не являются столь совершенными. При передаче данных могут возникать помехи. Помехоустойчивость – способность системы осуществлять прием информации в условиях наличия помех в линии связи и искажений во внутри аппаратных трактах. Помехоустойчивость обеспечивает надежность и достоверность передаваемой информации (данных).Управление правильностью передачи информации выполняется с помощью помехоустойчивого кодирования. Есть коды, обнаруживающие ошибки, и корректирующие коды, которые еще и исправляют ошибки. Помехозащищенность достигается с помощью введения избыточности, дополнительных битов. В симплексных каналах связи устраняют ошибки с помощью корректирующих кодов. В дуплексных–достаточно применения кодов, обнаруживающих ошибки. [1]

Цель данной курсовой работы: Ознакомление с помехоустойчивым кодированием и изучение кода Хемминга.

1) Ознакомиться с видами помехоустойчивого кодирования;

2) Ознакомиться с кодом Хемминга, как с одним из видов помехоустойчивого кодирования;

3) Изучить алгоритм построения кода Хемминга.

Объект исследования : помехоустойчивое кодирование.

Предмет исследования : код Хемминга.

Данная курсовая работа состоит из титульного листа, оглавления,введения, двух глав (теоретической и практической), заключения и списка литературы.

Глава 1. Теоретические основы изучения помехоустойчивого кодирования

1.1. Виды помехоустойчивого кодирования

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

Рис. 1.Помехи и их источники

Внешние источники помех вызывают в основном импульсные помехи, а внутренние –флуктуационные. Помехи, накладываясь на видеосигнал, приводят к двум типам искажений: краевыеи дробления. Краевые искажения связаны со смещением переднего или заднего фронта импульса.Дробление связано с дроблением единого видеосигнала на некоторое количество более коротких сигналов [2].

Приведем классификацию помехоустойчивых кодов.

1) Обнаруживающие ошибки:

• с проверкой на четность;
• корреляционные;
• Хэмминга;
• БЧХ;

2) Корректирующие коды:

А) С пороговым декодированием;

Б) По макс. правдоподобия;

В) С последовательным декодированием.

Теперь рассмотрим более подробно каждый вид кодирования.

Код с проверкой на четность .

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

В каждом пакет данных есть один бит четности, или, так называемый, паритетный бит. Этот бит устанавливается во время записи (или отправки) данных, и затем рассчитывается и сравнивается во время чтения (получения) данных. Он равен сумме по модулю 2 всех бит данных в пакете. То есть число единиц в пакете всегда будет четно. Изменение этого бита (например с 0 на 1) сообщает о возникшей ошибке.

Начальные данные: 1111

Данные после кодирования: 11110 (1 + 1 + 1 + 1 = 0 (mod 2))

Принятые данные: 10110 (изменился второй бит)

Как мы видим, количество единиц в принятом пакете нечетно, следовательно, при передаче произошла ошибка [3].

Корреляционные коды (код с удвоением ).

Вместо комбинации 1010011 передается 10011001011010. Ошибка обнаруживается в том случае, если в парных элементах будут одинаковые символы 00 или 11 (вместо 01 и 10) [2].

Код с постоянным весом.

Одним из простейших блочных неразделимых кодов является код с постоянным весом. Примером такого кода может служить семибитный телеграфный код МТК–3, в котором каждая разрешенная кодовая комбинация содержит три единицы и четыре нуля (рис.2). Весом кодовой комбинации называют число содержащихся в ней единиц. В рассматриваемом коде вес кодовых комбинаций равен трем.

Число разрешенных кодовых комбинаций в кодах с постоянным весом определяется как количество сочетаний из n символов по g и равно

Рис.2. Примеры разрешенных и запрещенных комбинаций кода МТК-3

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

Прием инверсного кода осуществляется в два этапа. На первом этапе суммируются единицы в первой основной группе символов. Если число единиц четное, то контрольные символы принимаются без изменения, если нечетное, то контрольные символы инвертируются. На втором этапе контрольные символы суммируются с информационными символами по модулю два. Нулевая сумма говорит об отсутствии ошибок. При ненулевой сумме, принятая комбинация бракуется. Покажем суммирование для принятых комбинаций без ошибок (1,3) и с ошибками (2,4).

Обнаруживающие способности данного кода достаточно велики. Данный код обнаруживает практически любые ошибки, кроме редких ошибок смещения, которые одновременно происходят как среди информационных символов, так и среди соответствующих контрольных. Например, при k =5, n=10 и . Коэффициент обнаружения будет составлять [2].

Недостатком кода Грея является его невесомость, т.е. вес единицы не определяется номером разряда. Информацию в таком виде трудно обрабатывать на ЭВМ. Декодирование кода также связано с большими затратами. Поэтому перед вводом в ЭВМ (или перед декодированием) код Грея преобразуется в простой двоичный код, который удобен для ЭВМ и легко декодируется.

Для перевода простого двоичного кода в код Грея нужно:

1. под двоичным числом записать такое же число со сдвигом вправо на один разряд (при этом младший разряд сдвигаемого числа теряется);
2. произвести поразрядное сложение двух чисел по модулю 2 (четности). [5].

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

1.2.Характеристика кода Хэмминга при помехоустойчивом кодировании

В середине 40-х годов Ричард Хемминг работал в знаменитых Лабораториях Белла на счётной машине Bell Model V. Это была электромеханическая машина, использующая релейные блоки,скорость которых была очень низка: один оборот за несколько секунд. Данные вводились в машине с помощью перфокарт, и поэтому в процессе чтения часто происходили ошибки. В рабочие дни использовались специальные коды, чтобы обнаруживать и исправлять найденные ошибки, при этом оператор узнавал об ошибке по свечению лампочек, исправлял и запускал машину. В выходные дни, когда не было операторов, при возникновении ошибки машина автоматически выходила из программы и запускала другую.

Р. Хемминг часто работал в выходные дни, и все больше и больше раздражался, потому что часто был должен перегружать свою программу из-за ненадежности перфокарт. На протяжении нескольких лет он проводил много времени над построением эффективных алгоритмов исправления ошибок. В 1950 году он опубликовал способ, который на сегодняшний день мы знаем как код Хемминга.[6.].

Код Хемминга, как и любой ( n,k ) код, содержит k информационных и избыточных символов. Избыточная часть кода строится таким образом, чтобы при декодировании можно было бы установить не только факт наличия ошибок в принятой – комбинации, но и указать номер позиции, в которой произошла ошибка. Это достигается за счет многократной проверки принятой комбинации на четность. Каждой проверкой должны охватываться часть информационных символов и один из избыточных символов. При каждой проверке получают двоичный контрольный символ. Если результат проверки дает четное число, то контрольному символу присваивается значение 0, если нечетное число– 1. В результате всех проверок получается p -разрядное двоичное число, указывающее номер искаженного символа. Для исправления ошибки достаточно лишь изменить значение данного символа на обратное. [7]

К ним обычно относятся коды с минимальным кодовым расстоянием исправляющие все одиночные ошибки, и коды с расстоянием исправляющие все одиночные и обнаруживающие все двойные ошибки. Длина кода Хэмминга:

(r – количество проверочных разрядов).

Характерной особенностью проверочной матрицы кода с является то, что ее столбцы представляют собой любые различные ненулевые комбинации длиной r .Например, при r =4 и n =5 для кода (15,11), проверочная матрица может иметь следующий вид (рис.3)

Рис.3. Проверочная матрица

Перестановкой столбцов, содержащих одну единицу, данную матрицу можно привести к виду(рис.4)

Рис. 4.Измененная матрица

Рис.5. Система проверочных уравнений

где - -проверочные разряды; - -информационные разряды

Двоичный код Хэмминга с кодовым расстоянием получается путем добавления к коду Хэмминга с одного проверочного разряда, представляющего собой результат суммирования по модулю два всех разрядов кодового слоя. Длина кода при этом разрядов, из которых являются проверочными.

Операция кодирования может выполняться в два этапа. На первом этапе определяется кодовая комбинация с использованием матрицы H, соответствующей коду с на втором — добавляется один проверочный разряд, в котором записывается результат суммирования по модулю два всех разрядов кодового слова, полученного на первом этапе. Операция декодирования также состоит из двух этапов. На первом вычисляется синдром, соответствующий коду на втором — проверяется последнее проверочное соотношение.[8]

1.3.Алгоритмы использования кода Хэмминга для нахождения ошибок

Рассмотрим алгоритм построения кода для исправления одиночной ошибки.

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

Вычисляют основные параметры кода m и n .

2.Определяем рабочие и контрольные позиции кодовой комбинации. Номера контрольных позиций определяются по закону , где i= 1,2,3,…т.е. они равны 1,2,4,8,16,…а остальные позиции являются рабочими.

3. Определяем значения контрольных разрядов (0 или 1) при помощи многократных проверок кодовой комбинации на четность. Количество проверок равно . В каждую проверку включается один контрольный и определенные проверочные биты. Если результат проверки дает четное число, то контрольному биту присваивается значение – 0, в противном случае – 1. Номера информационных бит, включаемых в каждую проверку, определяются по двоичному коду натуральных n -чисел разрядностью – m (табл. 2, для m = 4) или при помощи проверочной матрицы H(mn), столбцы которой представляют запись в двоичной системе всех целых чисел от 1 до перечисленных в возрастающем порядке.

Количество разрядов m – определяет количество проверок.

В первую проверку включают коэффициенты, содержащие 1 в младшем (первом) разряде, т.е. b1 , b3 , b5 и т.д.

Во вторую проверку включают коэффициенты, содержащие 1 во втором разряде, т.е. b2 , b3 , b6 и т.д.

В третью проверку –коэффициенты которые содержат 1 в третьем разряде и т.д.

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

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

В некоторых предложениях, взятых из естественного языка, достаточно сильно исказить небольшое число букв (например, считать эти буквы неопределенными), чтобы смысл был полностью искажен. Известно [I], что избыточность английского языка достигает 70%, однако нельзя сказать, что избыточность вводится в английский текст оптимально с точки зрения возможности исправления и обнаружения ошибок. Основной задачей теории кодирования в настоящее время является повышение надежности систем связи и вычислительных систем

Фиг. 1.1. Модель системы связи.

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

Ниже рассматривается несколько примеров простых кодов, обнаруживающих или исправляющих ошибки.

Таблица 1.1 (см. скан) Пример представления десятичных цифр

где в данном случае знак означает сложение по модулю 2, т.е. если сумма в правой части (1.1) четна, и если она нечетна. Предположим, что вместо последовательностей длины используются последовательности длины Допустим, что в процессе передачи или обработки одной из таких последовательностей, содержащей один избыточный двоичный символ, возникла ошибка в одном из двоичных символов. Как видно из формулы (1.1), в неискаженной последовательности число символов 1 всегда четно, а при возникновении ошибки в одном из символов это число становится нечетным. Это позволяет обнаруживать возникновение одиночных ошибок. Символ

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

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

где знак обозначает сложение по модулю 2. Если то это означает, что в двоичном символе произошла ошибка; если то двоичный символ передан без ошибок. Используя матрицу из левой части (1.2), определим

Из формул (1.2) и (1.3) получаем

По предположению только один из символов может быть равен 1. При отсутствии ошибок, когда имеем

Далее рассмотрим случай, когда а остальные шесть символов равны 0. Заметим, во-первых, что все столбцы матрицы

из левой части (1.4) различны, а во-вторых, что столбец этой матрицы представляет собой двоичную запись номера (самый младший разряд двоичного представления числа является верхним элементом столбца). При сделанных выше предположениях вектор-столбец совпадает с столбцом матрицы Следовательно, номер искаженного двоичного символа может быть найден следующим образом: . С помощью равенства находим правильные двоичные символы Множество двоичных последовательностей удовлетворяющих соотношению (1.2) и

называемых обычно кодовыми векторами, называется кодом Хэмминга длины 7 [3].

Утверждение 1.1. Если последовательности удовлетворяют соотношению (1.2) (т. е. то число значений индекса таких, что (это число называется расстоянием Хэмминга [3] между векторами не меньше трех (символ означает транспонирование).

Краткое доказательство. Число ненулевых компонент вектора называют весом этого вектора. Пусть произвольный вектор веса 1 или 2. Так как все столбцы матрицы различны и ни один из них не является нулевым, то Вместе с тем по условиям утверждения Наконец, заметим, что вес вектора совпадает с (здесь 0 — нулевой вектор).

Утверждение 1.2. Для любого двоичного вектора У длины 7 найдется такой кодовый вектор X, что

Краткое доказательство. Если У — кодовый вектор, то Предположим, что У не является кодовым вектором. Пусть двоичный вектор длины Среди столбцов матрицы существует ровно один столбец, в точности совпадающий с Пусть номер этого столбца. Возьмем в качестве вектора X вектор, отличающийся от У только компонентой. Тогда

Утверждение 1.3. В случае никакой код, имеющий два или менее проверочных символа, не может исправлять одиночные ошибки. В этом смысле код Хэмминга длины 7 является наилучшим среди кодов, исправляющих одиночные ошибки.

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

расстоянии Хэмминга 1 и менее от каждого кодового слова, не должны пересекаться. Если длина кода равна то число векторов, находящихся на расстоянии 1 и менее от кодового слова, равно Так как общее число двоичных векторов длины равно то для любого кода, исправляющего одиночные ошибки, должно выполняться неравенство откуда следует справедливость доказываемого утверждения.

По матрице из примера 1.4 построим матрицу следующим образом:

Совокупность всех двоичных векторов X длины 8, удовлетворяющих условию называется расширением кода из примера 1.4.

Утверждение 1.4. Расширение кода из примера 1.4 исправляет одиночные ошибки и в то же время обнаруживает двойные ошибки (т. е. ошибки в любых двух компонентах кодового вектора).

Идея доказательства. Вначале, используя утверждение 1.1, нужно показать, что расстояние Хэмминга между любыми двумя различными кодовыми векторами не меньше четырех. Основываясь на этом, далее следует доказать, что рассматриваемый код исправляет одиночные и обнаруживает двойные ошибки (в общем случае связь между минимальным значением расстояния Хэмминга и способностью кода исправлять и обнаруживать ошибки устанавливается в разд. 1.3).

При изучении корректирующей способности кода Хэмминга из примера 1.3 и его расширения из утверждения 1.4 для нас существенным было лишь то, что все столбцы матрицы различны и все они являются ненулевыми. Аналогично можно построить коды для любого . В общем случае коды Хэмминга и их расширения рассматриваются в задаче 3.2, примере 3.5 и разд. 4.1.

Читайте также:

  
• В чем значение ритмичности процессов жизнедеятельности кратко
  
• Анализ сонета шекспира 90 кратко
  
• Докажите что реформы кемаля ататюрка изменили традиционное общество турции кратко
  
• Почему снегиря так назвали кратко
  
• Дробный и систематический анализ в аналитической химии кратко