Каково должно быть расстояние хэмминга между двумя любыми кодами чтобы можно было исправить 2 ошибки - Ремонт и установка крупной бытовой техники

Перейти к контенту

Информатика 11 класс Поляков Углубленный ГДЗ § 2. Передача данных

§ 2. Передача данных ГДЗ по Информатике 11 класс. Углубленный уровень. В 2 ч. Поляков К.Ю.

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

Ответ

Расстояние Хэмминга — число позиций, в которых соответствующие символы двух кодовых слов одинаковой длины различны. Если рассматривать два кодовых слова, (пример на картинке ниже, 1 0 1 1 0 0 1 и 1 0 0 1 1 0 1) видно что они отличаются друг от друга на два символа, соответственно расстояние Хэмминга равно 2. Кратность исправляемых ошибок и обнаруживаемых, связано минимальным расстоянием Хэмминга.

Источник

Корректирующие (или помехоустойчивые) коды — это коды, которые могут обнаружить и, если повезёт, исправить ошибки, возникшие при передаче данных. Даже если вы ничего не слышали о них, то наверняка встречали аббревиатуру CRC в списке файлов в ZIP-архиве или даже надпись ECC на планке памяти. А кто-то, может быть, задумывался, как так получается, что если поцарапать DVD-диск, то данные всё равно считываются без ошибок. Конечно, если царапина не в сантиметр толщиной и не разрезала диск пополам.

Как нетрудно догадаться, ко всему этому причастны корректирующие коды. Собственно, ECC так и расшифровывается — «error-correcting code», то есть «код, исправляющий ошибки». А CRC — это один из алгоритмов, обнаруживающих ошибки в данных. Исправить он их не может, но часто это и не требуется.

Давайте же разберёмся, что это такое.

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

Внимание! Много текста и мало картинок. Я постарался всё объяснить, но без карандаша и бумаги текст может показаться немного запутанным.

Каналы с ошибкой

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

Ошибка — это маловероятное событие (а иначе зачем нам такой канал вообще, где одни ошибки?), а значит, вероятность двух ошибок меньше, а трёх уже совсем мала. Мы можем выбрать для себя некоторую приемлемую величину вероятности, очертив границу «это уж точно невозможно». Это позволит нам сказать, что в канале возможно не более, чем $k$ ошибок. Это будет характеристикой канала связи.

Для простоты введём следующие обозначения. Пусть данные, которые мы хотим передавать, — это двоичные последовательности фиксированной длины. Чтобы не запутаться в нулях и единицах, будем иногда обозначать их заглавными латинскими буквами ( $A$ , $B$ , $C$ , …). Что именно передавать, в общем-то неважно, просто с буквами в первое время будет проще работать.

Кодирование и декодирование будем обозначать прямой стрелкой ( $rightarrow$ ), а передачу по каналу связи — волнистой стрелкой ( $rightsquigarrow$ ). Ошибки при передаче будем подчёркивать.

Например, пусть мы хотим передавать только сообщения $A=0$ и $B=1$ . В простейшем случае их можно закодировать нулём и единицей (сюрприз!):

$ begin{aligned} A &to 0, B &to 1. end{aligned} $

Передача по каналу, в котором возникла ошибка будет записана так:

$ A to 0 rightsquigarrow underline{1} to B. $

Цепочки нулей и единиц, которыми мы кодируем буквы, будем называть кодовыми словами. В данном простом случае кодовые слова — это $0$ и $1$ .

Код с утроением

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

$ begin{aligned} A &to 00, B &to 11. end{aligned} $

Правда, это нам не очень поможет. В самом деле, рассмотрим канал с одной возможной ошибкой:

$ A to 00 rightsquigarrow 0underline{1} to ?. $

Какие выводы мы можем сделать, когда получили $01$ ? Понятно, что раз у нас не две одинаковые цифры, то была ошибка, но вот в каком разряде? Может, в первом, и была передана буква $B$ . А может, во втором, и была передана $A$ .

То есть, получившийся код обнаруживает, но не исправляет ошибки. Ну, тоже неплохо, в общем-то. Но мы пойдём дальше и будем теперь утраивать цифры.

$ begin{aligned} A &to 000, B &to 111. end{aligned} $

Проверим в деле:

$ A to 000 rightsquigarrow 0underline{1}0 to A?. $

Получили $010$ . Тут у нас есть две возможности: либо это $B$ и было две ошибки (в крайних цифрах), либо это $A$ и была одна ошибка. Вообще, вероятность одной ошибки выше вероятности двух ошибок, так что самым правдоподобным будет предположение о том, что передавалась именно буква $A$ . Хотя правдоподобное — не значит истинное, поэтому рядом и стоит вопросительный знак.

Если в канале связи возможна максимум одна ошибка, то первое предположение о двух ошибках становится невозможным и остаётся только один вариант — передавалась буква $A$ .

Про такой код говорят, что он исправляет одну ошибку. Две он тоже обнаружит, но исправит уже неверно.

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

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

Расстояния между кодами

Рассмотрим поподробнее код с утроением. Итак, мы получили работающий код, который исправляет одиночную ошибку. Но за всё хорошее надо платить: он кодирует один бит тремя. Не очень-то и эффективно.

И вообще, почему этот код работает? Почему нужно именно утраивать для устранения одной ошибки? Наверняка это всё неспроста.

Давайте подумаем, как этот код работает. Интуитивно всё понятно. Нолики и единички — это две непохожие последовательности. Так как они достаточно длинные, то одиночная ошибка не сильно портит их вид.

Пусть мы передавали $000$ , а получили $001$ . Видно, что эта цепочка больше похожа на исходные $000$ , чем на $111$ . А так как других кодовых слов у нас нет, то и выбор очевиден.

Но что значит «больше похоже»? А всё просто! Чем больше символов у двух цепочек совпадает, тем больше их схожесть. Если почти все символы отличаются, то цепочки «далеки» друг от друга.

Можно ввести некоторую величину $d(alpha, beta)$ , равную количеству различающихся цифр в соответствующих разрядах цепочек $alpha$ и $beta$ . Эту величину называют расстоянием Хэмминга. Чем больше это расстояние, тем меньше похожи две цепочки.

Например, $d(010, 010) = 0$ , так как все цифры в соответствующих позициях равны, а вот $d(010101, 011011) = 3$ .

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

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

Достаточно разумные требования.

Математически это можно записать так (нам это не пригодится, просто ради интереса посмотрим):

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

Окрестности

Таким образом, разные цепочки мы считаем точками в каком-то воображаемом пространстве, и теперь мы умеем находить расстояния между ними. Правда, если попытаться сколько нибудь длинные цепочки расставить на листе бумаги так, чтобы расстояния Хэмминга совпадали с расстояниями на плоскости, мы можем потерпеть неудачу. Но не нужно переживать. Всё же это особое пространство со своими законами. А слова вроде «расстояния» лишь помогают нам рассуждать.

Пойдём дальше. Раз мы заговорили о расстоянии, то можно ввести такое понятие как окрестность. Как известно, окрестность какой-то точки — это шар определённого радиуса с центром в ней. Шар? Какие ещё шары! Мы же о кодах говорим.

Но всё просто. Ведь что такое шар? Это множество всех точек, которые находятся от данной не дальше, чем некоторое расстояние, называемое радиусом. Точки у нас есть, расстояние у нас есть, теперь есть и шары.

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

$ {000, 100, 010, 001}. $

Да, вот так странно выглядят шары в пространстве кодов.

А теперь посмотрите. Это же все возможные коды, которые мы получим в канале в одной ошибкой, если отправим $000$ ! Это следует прямо из определения окрестности. Ведь каждая ошибка заставляет цепочку измениться только в одном разряде, а значит удаляет её на расстояние 1 от исходного сообщения.

Аналогично, если в канале возможны две ошибки, то отправив некоторое сообщение $x$ , мы получим один из кодов, который принадлежит окрестности $x$ радиусом 2.

Тогда всю нашу систему декодирования можно построить так. Мы получаем какую-то цепочку нулей и единиц (точку в нашей новой терминологии) и смотрим, в окрестность какого кодового слова она попадает.

Сколько ошибок может исправить код?

Чтобы код мог исправлять больше ошибок, окрестности должны быть как можно шире. С другой стороны, они не должны пересекаться. Иначе если точка попадёт в область пересечения, непонятно будет, к какой окрестности её отнести.

В коде с удвоением между кодовыми словами $00$ и $11$ расстояние равно 2 (оба разряда различаются). А значит, если мы построим вокруг них шары радиуса 1, то они будут касаться. Это значит, точка касания будет принадлежать обоим шарам и непонятно будет, к какому из них её отнести.

Именно это мы и получали. Мы видели, что есть ошибка, но не могли её исправить.

Что интересно, точек касания в нашем странном пространстве у шаров две — это коды $01$ и $10$ . Расстояния от них до центров равны единице. Конечно же, в обычно геометрии такое невозможно, поэтому рисунки — это просто условность для более удобного рассуждения.

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

Минимальный зазор между шарами равен 1, так как у нас расстояния всегда целые (ну не могут же две цепочки отличаться в полутора разрядах).

В общем случае получаем следующее.

Этот очевидный результат на самом деле очень важен. Он означает, что код с минимальным кодовым расстоянием $d_{min}$ будет успешно работать в канале с $k$ ошибками, если выполняется соотношение

$d_{min} geqslant 2k+1.$

Полученное равенство позволяет легко определить, сколько ошибок будет исправлять тот или иной код. А сколько код ошибок может обнаружить? Рассуждения такие же. Код обнаруживает $k$ ошибок, если в результате не получится другое кодовое слово. То есть, кодовые слова не должны находиться в окрестностях радиуса $k$ других кодовых слов. Математически это записывается так:

$d_{min}geqslant k + 1.$

Рассмотрим пример. Пусть мы кодируем 4 буквы следующим образом.

$ begin{aligned} A to 10100, B to 01000, C to 00111, D to 11011. end{aligned} $

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

	A	B	C	D
A	—	3	3	4
B	3	—	4	3
C	3	4	—	3
D	4	3	3	—

Минимальное расстояние $d_{min}=3$ , а значит $3geqslant2k+1$ , откуда получаем, что такой код может исправить до $k=1$ ошибок. Обнаруживает же он две ошибки.

Рассмотрим пример:

$ A to 10100 rightsquigarrow 101underline{1}0. $

Чтобы декодировать полученное сообщение, посмотрим, к какому символу оно ближе всего.

$ begin{aligned} A:, d(10110, 10100) &= 1, B:, d(10110, 01000) &= 4, C:, d(10110, 00111) &= 2, D:, d(10110, 11011) &= 3. end{aligned} $

Минимальное расстояние получилось для символа $A$ , значит вероятнее всего передавался именно он:

$ A to 10100 rightsquigarrow 101underline{1}0 to A?. $

Итак, этот код исправляет одну ошибку, как и код с утроением. Но он более эффективен, так как в отличие от кода с утроением здесь кодируется уже 4 символа.

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

Для декодирования можно было бы использовать таблицу, в которой указывались бы все возможные принимаемые сообщения, и кодовые слова, которым они соответствуют. Но такая таблица получилась бы очень большой. Даже для нашего маленького кода, который выдаёт 5 двоичных цифр, получилось бы $2^5 = 32$ варианта возможных принимаемых сообщений. Для более сложных кодов таблица будет значительно больше.

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

Интерлюдия: поле GF(2)

Для изложения дальнейшего материала нам потребуются матрицы. А при умножении матриц, как известно мы складываем и перемножаем числа. И тут есть проблема. Если с умножением всё более-менее хорошо, то как быть со сложением? Из-за того, что мы работаем только с одиночными двоичными цифрами, непонятно, как сложить 1 и 1, чтобы снова получилась одна двоичная цифра. Значит вместо классического сложения нужно использовать какое-то другое.

Введём операцию сложения как сложение по модулю 2 (хорошо известный программистам XOR):

$ begin{aligned} 0 + 0 &= 0, 0 + 1 &= 1, 1 + 0 &= 1, 1 + 1 &= 0. end{aligned} $

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

Множество из двух элементов ${0, 1}$ с операциями, введёнными так, как мы это сделали, называется полем Галуа GF(2). GF — это Galois field, а 2 — количество элементов.

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

$ x + x = 0. $

Это свойство прямо следует из определения.

$ x + y = x - y. $

А в этом можно убедиться, прибавив $y$ к обеим частям равенства. Это свойство, в частности означает, что мы можем переносить в уравнении слагаемые в другую сторону без смены знака.

Проверяем корректность

Вернёмся к коду с утроением.

$ begin{aligned} A &to 000, B &to 111. end{aligned} $

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

Пусть мы приняли вектор-строку $x$ из трёх цифр. (Стрелочки над векторами рисовать не будем, так как у нас почти всё — это вектора или матрицы.)

$dots rightsquigarrow x = (x_1, x_2, x_3). $

Математически равенство всех трёх цифр можно записать как систему:

$left{ begin{aligned} x_1 &= x_2, x_2 &= x_3. end{aligned} right.$

Или, если воспользоваться свойствами сложения в GF(2), получаем

$left{ begin{aligned} x_1 + x_2 &= 0, x_2 + x_3 &= 0. end{aligned} right.$

Или

$left{ begin{aligned} 1cdot x_1 + 1cdot x_2 + 0cdot x_3 &= 0, 0cdot x_1 + 1cdot x_2 + 1cdot x_3 &= 0. end{aligned} right.$

В матричном виде эта система будет иметь вид

$ Hx^T = 0, $

где

$ H = begin{pmatrix} 1 & 1 & 0 0 & 1 & 1 end{pmatrix}. $

Транспонирование здесь нужно потому, что $x$ — это вектор-строка, а не вектор-столбец. Иначе мы не могли бы умножать его справа на матрицу.

Будем называть матрицу $H$ проверочной матрицей. Если полученное сообщение — это корректное кодовое слово (то есть, ошибки при передаче не было), то произведение проверочной матрицы на это сообщение будет равно нулевому вектору.

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

Кодирование

Итак, у нас есть система для проверки

$left{ begin{aligned} x_1 + x_2 &= 0, x_2 + x_3 &= 0. end{aligned} right.$

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

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

$ H = begin{pmatrix} 1 & 0 & 1 & 0 & 0 0 & 1 & 1 & 0 & 1 0 & 0 & 0 & 1 & 1 end{pmatrix}. $

Соответствующая система имеет вид:

$left{ begin{aligned} x_1 + x_3 &= 0, x_2 + x_3 + x_5 &= 0, x_4 + x_5 &= 0. end{aligned} right.$

Чтобы найти кодовые слова соответствующего кода нужно её решить.

В силу линейности сумма двух решений системы тоже будет решением системы. Это легко доказать. Если $a$ и $b$ — решения системы, то для их суммы верно

$H(a+b)^T=Ha^T+Hb^T=0+0=0,$

что означает, что она тоже — решение.

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

Выразим сперва все зависимые слагаемые. Их столько же, сколько и уравнений. Выражать надо так, чтобы справа были только независимые. Проще всего выразить $x_1, x_2, x_4$ .

Если бы нам не так повезло с системой, то нужно было бы складывая уравнения между собой получить такую систему, чтобы какие-то три переменные встречались по одному разу. Ну, или воспользоваться методом Гаусса. Для GF(2) он тоже работает.

Итак, получаем:

$left{ begin{aligned} x_1 &= x_3, x_2 &= x_3 + x_5, x_4 &= x_5. end{aligned} right.$

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

$begin{aligned} x_3=1, x_5=0:quad x_1=1, x_2=1, x_4=0 Rightarrow x^{(1)} = (1, 1, 1, 0, 0), x_3=0, x_5=1:quad x_1=0, x_2=1, x_4=1 Rightarrow x^{(2)} = (0, 1, 0, 1, 1). end{aligned}$

Всевозможные суммы этих независимых решений (а именно они и будут кодовыми векторами) можно получить так:

$a_1 x^{(1)}+a_2 x^{(2)},$

где $a_1, a_2$ равны либо нулю или единице. Так как таких коэффициентов два, то всего возможно $2^2=4$ сочетания.

Но посмотрите! Формула, которую мы только что получили — это же снова умножение матрицы на вектор.

$(a_1, a_2)cdot begin{pmatrix} 1 & 1 & 1 & 0 & 0 0 & 1 & 0 & 1 & 1 end{pmatrix} = aG.$

Строчки здесь — линейно независимые решения, которые мы получили. Матрица $G$ называется порождающей. Теперь вместо того, чтобы сами составлять таблицу кодирования, мы можем получать кодовые слова простым умножением на матрицу:

$ a to aG. $

Найдём кодовые слова для этого кода. (Не забываем, что длина исходных сообщений должна быть равна 2 — это количество найденных решений.)

$ begin{aligned} 00 &to 00000, 01 &to 01011, 10 &to 11100, 11 &to 10111. end{aligned} $

Итак, у нас есть готовый код, обнаруживающий ошибки. Проверим его в деле. Пусть мы хотим отправить 01 и у нас произошла ошибка при передаче. Обнаружит ли её код?

$a=01 to aG=01011 rightsquigarrow x=01underline{1}11 to Hx^T = (110)^T neq 0.$

А раз в результате не нулевой вектор, значит код заподозрил неладное. Провести его не удалось. Ура, код работает!

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

$G=begin{pmatrix}1&1&1end{pmatrix}.$

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

Ошибка по синдрому

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

Для начала введём такое понятие, как вектор ошибки. Это вектор, на который отличается принятое сообщение от кодового слова. Пусть мы получили сообщение $x$ , а было отправлено кодовое слово $v$ . Тогда вектор ошибки по определению

$ e = x - v. $

Но в странном мире GF(2), где сложение и вычитание одинаковы, будут верны и соотношения:

$ begin{aligned} v &= x + e, x &= v + e. end{aligned} $

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

Как мы уже говорили раньше, если мы получили сообщение $x$ с ошибкой, то $Hx^Tneq 0$ . Но ведь векторов, не равных нулю много! Быть может то, какой именно ненулевой вектор мы получили, подскажет нам характер ошибки?

Назовём результат умножения на проверочную матрицу синдромом:

$ s(x)=Hx^T.$

И заметим следующее

$ s(x) = Hx^T = H(v+e)^T = He^T = s(e). $

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

Разложим все возможные сообщения, которые мы можем получить из канала связи, по кучкам в зависимости от синдрома. Тогда из последнего соотношения следует, что в каждой кучке будут вектора с одной и той же ошибкой. Причём вектор этой ошибки тоже будет в кучке. Вот только как его узнать?

А очень просто! Помните, мы говорили, что у нескольких ошибок вероятность ниже, чем у одной ошибки? Руководствуясь этим соображением, наиболее правдоподобным будет считать вектором ошибки тот вектор, у которого меньше всего единиц. Будем называть его лидером.

Давайте посмотрим, какие синдромы дают всевозможные 5-элементные векторы. Сразу сгруппируем их и подчеркнём лидеров — векторы с наименьшим числом единиц.

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

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

Лидеры для всех возможных одиночных ошибок находятся в отдельных строках, а значит код может исправить любую одиночную ошибку. Ну, что же… Попробуем в этом убедиться.

$a=01 to aG=01011 rightsquigarrow x=01underline{1}11 to s(x)=Hx^T = (110)^T to e=(00100).$

Вектор ошибки равен $(00100)$ , а значит ошибка в третьем разряде. Как мы и загадали.

Ура, всё работает!

Что же дальше?

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

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

Если вас заинтересовали подробности, то можете почитать замечательную книжку Аршинова и Садовского «Коды и математика». Там изложено гораздо больше, чем представлено в этой статье. Если интересует математика кодирования — то поищите «Теория и практика кодов, контролирующих ошибки» Блейхута. А вообще, материалов по этой теме довольно много.

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

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

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

Рассмотрим пример CD диска. Там информация хранится прямо на поверхности диска, в углублениях, из-за того, что все дорожки на поверхности, часто диск хватаем пальцами, елозим по столу и из-за этого без помехоустойчивого кодирования, информацию извлечь не получится.

Использование кодирования позволяет извлекать информацию без потерь даже с поврежденного CD/DVD диска, когда какая либо область становится недоступной для считывания.

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

запрос повторной передачи (Automatic Repeat reQuest, ARQ): с помощью помехоустойчивого кода выполняется только обнаружение ошибок, при их наличии производится запрос на повторную передачу пакета данных;
прямое исправление ошибок (Forward Error Correction, FEC): производится декодирование помехоустойчивого кода, т. е. исправление ошибок с его помощью.

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

Исправление ошибок в помехоустойчивом кодировании

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

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

Допустим есть 4 символа информации, А, B, С,D, и эту информацию повторяем несколько раз. В процессе передачи информации по каналу связи, где-то возникла ошибка. Есть три пакета (A1B1C1D1|A2B2C2D2|A3B3C3D3), которые должны нести одну и ту же информацию.

мажоритарный метод

Но из картинки справа, видно, что второй символ (B1 и C1) они отличаются друг от друга, хотя должны были быть одинаковыми. То что они отличаются, говорит о том, что есть ошибка.

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

Для исправления ошибок нужно, как минимум 3 пакета информации, для обнаружения, как минимум 2 пакета информации.

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

Первый параметр, скорость кода R характеризует долю информационных («полезных») данных в сообщении и определяется выражением: R=k/n=k/m+k

где n – количество символов закодированного сообщения (результата кодирования);
m – количество проверочных символов, добавляемых при кодировании;
k – количество информационных символов.

Параметры n и k часто приводят вместе с наименованием кода для его однозначной идентификации. Например, код Хэмминга (7,4) значит, что на вход кодера приходит 4 символа, на выходе 7 символов, Рида-Соломона (15, 11) и т.д.

Второй параметр, кратность обнаруживаемых ошибок – количество ошибочных символов, которые код может обнаружить.

Третий параметр, кратность исправляемых ошибок – количество ошибочных символов, которые код может исправить (обозначается буквой t).

Контроль чётности

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

Если нечетное количество единиц, добавляем 0.

1 0 1 0 0 1 0 0 | 0

Если четное количество единиц, добавляем 1.

1 1 0 1 0 1 0 0 | 1

Если принятый бит чётности не совпадает с рассчитанным битом чётности, то считается, что произошла ошибка.

1 1 0 0 0 1 0 0 | 1

Под кратностью понимается, всевозможные ошибки, которые можно обнаружить. В этом случае, кратность исправляемых ошибок 0, так как мы не можем исправить ошибки, а кратность обнаруживаемых 1.

Есть последовательность 0 и 1, и из этой последовательности составим прямоугольную матрицу размера 4 на 4. Затем для каждой строки и столбца посчитаем бит четности.

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

прямоугольный код

И если в процессе передачи информации допустим ошибку (ошибка нолик вместо единицы, желтым цветом), начинаем делать проверку. Нашли ошибку во втором столбце, третьей строке по координатам. Чтобы исправить ошибку, просто инвертируем 1 в 0, тем самым ошибка исправляется.

Этот прямоугольный код исправляет все одно-битные ошибки, но не все двух-битные и трех-битные.

Рассчитаем скорость кода для:

1 1 0 0 0 1 0 0 | 1

Здесь R=8/9=0,88

И для прямоугольного кода:

Здесь R=16/24=0,66 (картинка выше, двадцать пятую единичку (бит четности) не учитываем)

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

Классификация помехоустойчивых кодов

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

По используемому алфавиту:

Двоичные. Оперируют битами.
Не двоичные (код Рида-Соломона). Оперируют более размерными символами. Если изначально информация двоичная, нужно эти биты превратить в символы. Например, есть последовательность 110 110 010 100 и нужно их преобразовать из двоичных символов в не двоичные, берем группы по 3 бита — это будет один символ, 6, 6, 2, 4 — с этими не двоичными символами работают не двоичные помехоустойчивые коды.

Блочные коды делятся на

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

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

систематический и несистематический код

Смотря на картинку выше, код 1 1 0 0 0 1 0 0 | 1 является систематическим, на вход поступило 8 бит, а на выходе кодера 9 бит, которые в явном виде содержат в себе 8 бит информационных и один проверочный.

Классификация помехоустойчивых кодов

Код Хэмминга

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

Код Хэмминга (7,4)

Код Хэмминга (7,4) — 4 бита на входе кодера и 7 на выходе, следовательно 3 проверочных бита. С 1 по 4 информационные биты, с 6 по 7 проверочные (см. табл. выше). Пятый проверочный бит y5, это сумма по модулю два 1-3 информационных бит. Сумма по модулю 2 это вычисление бита чётности.

Декодирование кода Хэмминга

Декодирование происходит через вычисление синдрома по выражениям:

Декодирование кода Хэмминга через синдром

Синдром это сложение бит по модулю два. Если синдром не нулевой, то исправление ошибки происходит по таблице декодирования:

Таблица декодирования. Код Хэмминга

Расстояние Хэмминга

расстояние хэмминга

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

Помехоустойчивые коды

Современные коды более эффективны по сравнению с рассматриваемыми примерами. В таблице ниже приведены Коды Боуза-Чоудхури-Хоквингема (БЧХ)

Коды Боуза-Чоудхури-Хоквингема (БЧХ)

Из таблицы видим, что там один класс кода БЧХ, но разные параметры n и k.

n — количество символов на входе.
k — количество символов на выходе.
t — кратность исправляемых ошибок.
Отношение k/n — скорость кода.
G (энергетический выигрыш) — величина, показывающая на сколько можно уменьшить отношение сигнал/шум (Eb/No) для обеспечения заданной вероятности ошибки.

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

Пример: помехоустойчивые коды и двоичная фазовая манипуляция (2-ФМн). На графике зависимость отношения сигнал шум (Eb/No) от вероятности ошибки. За счет применения помехоустойчивых кодов улучшается помехоустойчивость.

График помехоустойчивых кодов

Из графика видим, код Хэмминга (7,4) на сколько увеличилась помехоустойчивость? Всего на пол Дб это мало, если применить код БЧХ (127, 64) выиграем порядка 4 дБ, это хороший показатель.

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

Чем расплачиваемся за помехоустойчивые коды? Добавили избыточность, соответственно эту избыточность тоже нужно передавать. Нужно: увеличивать пропускную способность канала связи, либо увеличивать длительность передачи.

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

Компромисс:

Достоверность vs полоса пропускания.
Мощность vs полоса пропускания.
Скорость передачи данных vs полоса пропускания

Необходимость чередования (перемежения)

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

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

Пример блочного перемежения:

Пример блочного перемежения кодов

На картинке, всего 5 блоков (с 1 по 25). Код работает исправляя ошибки в рамках одного блока (если в одном блоке 1 ошибка, код его исправит, а если две то нет). В канал связи отдается информация не последовательно, а в перемешку. На выходе кодера сформировались 5 блоков и эти 5 блоков будем отдавать не по очереди а в перемешку. Записали всё по строкам, но считывать будем, чтобы отправлять в канал связи, по столбцам. Информация в блоках перемешалась. В канале связи возникла ошибка и мы потеряли большой кусок. В процессе приема, мы опять составляем таблицу, записываем по столбцам, но считываем по строкам. За счет того, что мы перемешали большое количество блоков между собой, групповая ошибка равномерно распределится по блокам.

Источник

Скорость передачи даных

Скорость передачи даных — это количество битов (байтов, Кбайт и т.д.), за 1 с).

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

Основная единица измерения скорости — биты в секунду (бит/с, англ. bps — bits per second). Для характеристики быстродействующих каналов применяют килобиты в секунду (Кбит/с) и мегабиты в секунду (Мбит/с), иногда используют байты в секунду (байт/с) и килобайты в секунду (Кбайт/с).

Информационный объём I данных, переданных по каналу за время t , вычисляется по формуле I = v • t, где v — скорость передачи данных. Например, если скорость передачи данных равна 512 000 бит/с, за 1 минуту можно передать файл объёмом

512 000 бит/с • 60 с = 30 720 000 битов = 3 840 000 байтов = 3075 Кбайт.

Обнаружение ошибок

В реальных каналах связи всегда присутствуют помехи, искажающие сигнал. В некоторых случаях ошибки допустимы, например, при прослушивании радиопередачи через Интернет небольшое искажение звука не мешает понимать речь. Однако чаще всего требуется обеспечить точную передачу данных. Для этого в первую очередь нужно определить факт возникновения ошибки и, если это произошло, передать блок данных ещё раз.

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

Простейший вариант — добавить 1 бит в конце блока данных, который будет равен 1, если в основном сообщении нечётное число единиц, и равен 0 для сообщения с чётным числом единиц. Этот дополнительный бит называется битом чётности. Бит чётности используется при передаче данных в сетях, проверка чётности часто реализуется аппаратно (с помощью электроники).

Например, пусть требуется передать два бита данных. Возможны всего 4 разных сообщения: 00, 01, 10 и 11. Первое и четвёртое из них содержат чётное число единиц (0 и 2), значит, бит чётности для них равен 0. Во втором и третьем сообщениях нечётное число единиц (1), поэтому бит чётности будет равен 1. Таким образом, сообщения с добавленным битом чётности будут выглядеть так:

000, 011, 101, 110.

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

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

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

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

Для обнаружения искажений в передаче файлов, когда может сразу возникнуть множество ошибок, используют другой метод — вычисляют контрольную сумму с помощью какой-нибудь хэш-функции (вспомните материал учебника для 10 класса). Чаще всего для этой цели применяют алгоритмы CRC (англ. Cyclic Redundancy Code — циклический избыточный код), а также криптографические хэш-функции MD5, SHA-1 и другие. Если контрольная сумма блока данных, вычисленная приёмником, не совпадает с контрольной суммой, записанной передающей стороной, то произошла ошибка.

Помехоустойчивые коды.

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

Пусть, например, нужно передать один бит, 0 или 1. Утроим его, добавив ещё два бита, совпадающих с первым. Таким образом, получаются два «правильных» сообщения:

000 и 111.

Теперь посмотрим, что получится, если при передаче одного из битов сообщения 000 произодёт ошибка и приёмник получит искажённое сообщение 001. Заметим, что оно отличается одним битом от 000 и двумя битами от второго возможного варианта — 111. Значит, скорее всего, произошла ошибка в последнем бите и сообщение нужно исправить на 000. Если приёмник получил 101, можно точно сказать, что произошла ошибка, однако попытка исправить её приведёт к неверному варианту, так как ближайшая «правильная» последовательность — это 111. Таким образом, такой код обнаруживает одну или две ошибки. Кроме того, он позволяет исправить (!) одну ошибку, т. е. является помехоустойчивым.

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

Выше мы фактически применили понятие «расстояния» между двумя кодами. В теории передачи информации эта величина называется расстоянием Хэмминга в честь американского математика Р. Хэмминга.

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

Например, расстояние d между кодами 001 и 100 равно

d(001, 100) = 2,

потому что они различаются в двух битах (эти биты подчёркнуты). В приведённом выше примере расстояние между «правильными» последовательностями (словами) равно d(000, 111) = 3. Такой код позволяет обнаружить одну или две ошибки и исправить одну ошибку.

В общем случае, если минимальное расстояние между «правильными» словами равно d, можно обнаружить от 1 до d — 1 ошибок, потому что при этом полученный код будет отличаться от всех допустимых вариантов. Для исправления r ошибок необходимо, чтобы выполнялось условие

d ≥ 2r +1.

Это значит, что слово, в котором сделано r ошибок, должно быть ближе к исходному слову (из которого оно получено искажением), чем к любому другому.

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

000 000 100 101

001 111 101 010

010 011 110 110

011 100 111 001

Расстояние Хэмминга между любыми двумя словами в таблице не менее 3, поэтому код обнаруживает две ошибки и позволяет исправить одну. Как же вычислить ошибочный бит?

Предположим, что было получено кодовое слово 011011. Определив расстояние Хэмминга до каждого из «правильных» слов, находим единственное слово 010011, расстояние до которого равно 1 (расстояния до остальных слов больше). Значит, скорее всего, это слово и было передано, но исказилось из-за помех.

На практике используют несколько более сложные коды, которые называются кодами Хэмминга. В них информационные и контрольные биты перемешаны, и за счёт этого можно сразу, без перебора, определить номер бита, в котором произошла ошибка. Наиболее известен семибитный код, в котором 4 бита — это данные, а 3 бита — контрольные. В нём минимальное расстояние между словами равно 3, поэтому он позволяет обнаружить две ошибки и исправить одну.

Вопросы и задания

1. В каких единицах измеряют скорость передачи данных?

2. Почему для любого канала связи скорость передачи данных ограничена?

3. Как вычисляется информационный объем данных, который можно передать за некоторое время?

4. В каких случаях при передаче данных допустимы незначительные ошибки?

5. Что такое избыточность сообщения? Для чего её можно использовать? Приведите примеры.

6. Как помехи влияют на передачу данных?

7. Что такое бит чётности? В каких случаях с помощью бита чётности можно обнаружить ошибку, а в каких — нельзя?

8. Можно ли исправить ошибку, обнаружив неверное значение бита четности?

9. Для чего используется метод вычисления контрольной суммы?

10. Какой код называют помехоустойчивым?

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

12. Как исправляется ошибка при использовании помехоустойчивого кода?

13. Сколько ошибок обнаруживает 7-битный код Хэмминга, описанный в конце параграфа, и сколько ошибок он позволяет исправить?

Подготовьте сообщение

а) «Алгоритмы CRC»

б) «Коды Хемминга»

Вернуться в главу

Block title

Вход на сайт

Поиск

Календарь

Архив записей
2015 Март 2015 Апрель

Статистика
Онлайн всего: 1 Гостей: 1 Пользователей: 0

Источник

Подборка по базе: баз данных 2021.pdf, СОГЛАСИЕ НА ОБРАБОТКУ ПЕРСОНАЛЬНЫХ ДАННЫХ.doc, Методика использования конвертации данных и планов обмена.doc, 2_Динамические структуры данных.doc, Реляционные базы данных (11 класс).pptx, Курсовая работа Защита персональных данных работников Мухина А. , Протокол учета пульсовых данных .docx, Алгоритмы и структуры данных Задание2.docx, Правовая информация о предоставлении персональных данных.docx, СОГЛАСИЕ НА ОБРАБОТКУ ПЕРСОНАЛЬНЫХ ДАННЫХ.docx

п 2 Передача данных
Харлова алина 11А
вопросы

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

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

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

теория
В4 в каких случаях с помощью бита четности можно обнаружить ошибку, а в каких – нельзя?
Бит чётности позволяет обнаруживать нечётное число ошибок (1, 3, 5, …), а ошибки в чётном количестве разрядов остаются незамеченными. Контроль применяется для небольших блоков данных (чаще всего — для каждого отдельного байта) и хорошо работает тогда, когда отдельные ошибки при передаче независимы одна от другой и встречаются редко.
назад

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

теория
В6 как вы думаете, почему для контроля передачи файлов используются контрольные суммы, а не бит четности?
Используя бит четности, легко и быстро работать, но если произошло более одной ошибки, то ее можно не заметить. Используя контрольные суммы каждая ошибка будет обнаружена, но при передаче и получении нужно будет вычислять эту контрольную сумму, что приведет к временным затратам.
назад

теория
В7 каково должно быть расстояние хэмминга между двумя любыми кодами, чтобы можно было исправить 2 ошибки?
Минимальное расстояние Хэмминга выбирается из условия расстояние равно d . Условие d>= 2r+1 , где r кол-во ошибок. Поэтому d>=5, может либо исправлять однократные ошибки, либо только обнаруживать однократные и двукратные ошибки.
назад

теория
В8 как исправляется ошибка при использовании помехоустойчивого кода?
Для исправления ошибки нужно к символу разряда в котором произошла ошибка прибавить единицу по модулю два.

теория
В9 какие достоинства и недостатки есть у кодов хэмминга с большим размером блоков?
Недостаток кода Хэмминга — некратность размера исходного блока кода и блока кода степени двойки. Это затрудняет обработку кодов Хэмминга на компьютерах, оперирующих блоками бит кратными степени двойки. Достоинство в том, что реализация алгоритма требует небольших ресурсов и может быть выполнена аппаратно. Исходными данными для кодирования является произвольная двоичная последовательность.

теория
1 доп Теория

Скорость передачи данных – это кол-во бит, которое передается по каналу связи за единицу времени.
Пропускная способность канала связи – наибольшая возможная скорость передачи данных, которую принципиально невозможно превысить.
Объем информации вычисляется по формуле I = u * t

назад
2 доп теория
Избыточность – включать в код « лишние биты », только для того чтобы найти ошибку.
Бит четности – дополнительный бит, используется при передачи данных в сетях. Ставится в конце блока данных, будет равен 1, если в основном сообщении нечетное число единиц, и равен 0, если сообщение с четным числом единиц. Применяется для небольших блоков данных. Контрольная сумма – другой метод обнаружения ошибок. Применяются алгоритмы CRC, хэш-функции. Если конт. сумма не совпадает то произошла ошибка.

назад
3 доп теория

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

…

Источник

The way to think about this is the following. Let $k_d$ be the number of errors you want to detect and $k_c$ be the number of errors you want to correct.

Any pair $(k_d,k_c)$ satisfying

$$
2k_c+k_d+1leq d_{min}
$$
can be simultaneously detected and corrected, you do not need the extra bit. If you like you can think of an inner radius of $k_c$ for correction and an outer shell of $k_d$ for detection and an extra distance of $1$ to ensure separation. Let $c$ be a codeword
and $c’$ be another at distance exactly $d_{min}$ away
$$
begin{array}{cccccc}
codeword & leftarrow~distance~rightarrow & leftarrow~distance~rightarrow & leftrightarrow &
leftarrow~distance~rightarrow & codeword \
mathbb{c}& ~cdots~k_c~cdots & cdots~ k_d ~cdots & 1 & cdots ~ k_c ~cdots & mathbb{c}’\
end{array}
$$

In the two extremes, we have by letting $k_c=0$ (don’t want to correct errors)
$$
k_d+1leq d_{min}
$$
and by letting $k_d=0$ (don’t want to detect errors)
$$
2k_c+1leq d_{min}.
$$

Источник

Ответ

Каналы с ошибкой

Код с утроением

Расстояния между кодами

Окрестности

Сколько ошибок может исправить код?

Интерлюдия: поле GF(2)

Проверяем корректность

Кодирование

Ошибка по синдрому

Что же дальше?

Исправление ошибок в помехоустойчивом кодировании

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

Контроль чётности

Классификация помехоустойчивых кодов

Код Хэмминга

Декодирование кода Хэмминга

Расстояние Хэмминга

Помехоустойчивые коды

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

Необходимость чередования (перемежения)

000 000 100 101

001 111 101 010

010 011 110 110

011 100 111 001

Block title

Вход на сайт

Поиск

Календарь

Архив записей

Статистика