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

💸 Как сделать бизнес проще, а карман толще?

Тот, кто работает в сфере услуг, знает — без ведения записи клиентов никуда. Мало того, что нужно видеть свое раписание, но и напоминать клиентам о визитах тоже. Проблема в том, что средняя цена по рынку за такой сервис — 800 руб/мес или почти 15 000 руб за год. И это минимальный функционал. Нашли самый бюджетный и оптимальный вариант: сервис VisitTime.
⚡️ Для новых пользователей первый месяц бесплатно. А далее 290 руб/мес, это в 3 раза дешевле аналогов. За эту цену доступен весь функционал: напоминание о визитах, чаевые, предоплаты, общение с клиентами, переносы записей и так далее.
✅ Уйма гибких настроек, которые помогут вам зарабатывать больше и забыть про чувство «что-то мне нужно было сделать».
Сомневаетесь? нажмите на текст, запустите чат-бота и убедитесь во всем сами!

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

на неприводимый полином

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

, так как он не содержит ни одного сомножителя кроме самого себя.

Боузом и Чоудхури доказано [10], что существует циклический код разрядности

При этом число проверочных символов удовлетворяет соотношению

может быть представлен в виде произведения неприводимых многочленов, степени которых являются делителями числа m от 1 до m включительно [7].

Соотношение между числом исправляемых ошибок s, числом информационных символов и числом проверочных символов регулируется формулой (5.6).

В таблице 5.4 приведены значения числа символов n в кодовой последовательности в зависимости от величины m, обеспечивающие кодовое расстояние

d =3 при исправлении одиночной ошибки. Для значений n = 3, 7, 15 по формуле (5.21) получены множества неприводимых многочленов

Не каждый многочлен даёт необходимое число остатков. Например, при исправлении однократной ошибки в 15-разрядном коде необходимо 15 остатков, полученных от деления кода ошибки на неприводимый полином. Однако, если выбран полином

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

даёт 15 остатков. Двоичное значение полинома

11001.

Образование циклического кода. n-разрядная кодовая комбинация имеет вид

. Положим, определены k, r и n. Тогда известны неприводимый многочлен

и многочлен

, соответствующий k -разрядной комбинации информационных символов

. Необходимо определить проверочные символы

. Один из методов образования кода заключается в следующем.

Многочлен

умножается на

. Это соответствует приписыванию r нулей справа в кодовой последовательности

. Произведение

делится на неприводимый полином

и получается

- разрядный остаток

. Все символы

в кодовой последовательности

замещаются символами остатка. В результате имеем многочлен

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

где

частное от деления

, остаток отсутствует.

Если в одном из разрядов символ изменил своё значение, остаток от деления

не равен нулю. Каждому ошибочному символу в кодовой комбинации

соответствует свой остаток (синдром).

Пусть n = 7, k = 4, r = 3. Выберем полином

1011, который дает 7 остатков. Положим,

. Неизвестными являются проверочные символы

Определим полиномы и соответствующие им коды

1110000,

1011. Остаток от деления полинома

на полином

равен

100.

Заменим нули проверочной части кода 1110000 кодом остатка и получим закодированную кодовую комбинацию 1110100, которому соответствует полином вида

. Разделив полином

на полином

, получим полином

000.

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

, то после деления кода с искажённым символом на код неприводимого многочлена получим синдром 011, что позволит инвертировать символ

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

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

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

. Процедура циклических сдвигов останавливается, если вес остатка

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

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

Пример 5.6 Пусть n = 7, k = 4, r = 3. Выберем полином

1011, который дает 7 остатков. Выберем из множества разрешённых кодовых комбинаций код 1110100 и внесём ошибку в 4-ый разряд 111 1 100. На рисунке 5.8 показана процедура определения искажённого символа. Разделив кодовую комбинацию с ошибкой на неприводимый полином, убедимся, что вес остатка

На рисунках 5.8 б, 5.8 в, 5.8 г показаны процедуры циклического сдвига и получения остатков, больших единицы. На рисунке 5.8.д демонстрируется, после очередного циклического сдвига и деления полученного кода на неприводимый полином остаток равен единице, следовательно, вес остатка w=1. Это значит последний сдвинутый символ ошибочный. Чтобы исправить ошибочный символ, последнюю кодовую комбинацию сложим по модулю 2 с остатком, рисунок 5.8.е. Произведя последовательно 4 раза циклический перенос вправо кодовой комбинации с исправленным символом, получим безошибочную кодовую комбинацию:

1. Булинский, А. В. Теория случайных процессов [Электронный ресурс] / А. В. Булинский, А. Н. Ширяев. - М.: ФИЗМАТЛИТ, 2005. - 408 с. - ISBN 5-9221-0335-0. https://znanium.com/bookread.php? book=405730

2. Панин, В. В. Основы теории информации [Электронный ресурс]: учебное пособие для вузов / В. В. Панин. - 4-е изд. (эл.). - М.: БИНОМ. Лаборатория знаний, 2012. - 438 с.: ил. - ISBN 978-5-9963-0759-3.

3. Миллер, Б. М. Теория случайных процессов в примерах и задачах [Электронный ресурс] / Б. М. Миллер, А. Р. Панков. - М.: ФИЗМАТЛИТ, 2007. - 320 с. - ISBN 978-5-9221-0206-3.

1. Левин Б.Р. Статистические основы радиотехники. – М.: Сов. Радио, 1968, книга 2, 504 с.

2. Колмогоров А. Н. Теория информации и теория алгоритмов.— М.: Наука, 1987.-304 с

3. Зюко А.Г., Кловский Д.Д., Назаров М.В., Финк Л.М. Теория передачи сигналов – М.: Радио и связь, 1986. – 304 с.

4. Р. Фано Передача информации. Статистическая теория связи. – М.: Мир, 1965. – 438 с.

5. Марпл.-мл. С.Л. Цифровой спектральный анализ и его приложения. – М.: Мир, 1990. – 384 с.

6. Шеннон К. Работы по теории информации и кибернетике. – М.: – ИЛ, 1963.– 830 с.

7. Березюк Н. Т., Андрущенко А. Г., Мощицкий С. С.. Кодирование информации –Харьков: Вища школа, 1978. – 252 с.

8. Гуров И.П. Основы теории информации и передачи сигналов. - СПб.: BHV-Санкт-Петербург, 2000. - 97 с.:

9. Темников Ф.Е., Афонин В.А., Дмитриев В.И.Теоретические основы информационной техники. – М.: Энергия, 1979. – 424 с.

10 Питерсон У., Уэлдон Э.. Коды, исправляющие ошибки. – М.: Мир, 1976. – 594 с.

11. Сидельников, В. М. Теория кодирования [Электронный ресурс] / В. М. Сидельников. - М.: ФИЗМАТЛИТ, 2008. - 324 с. - ISBN 978-5-9221-0943-7.

12. Основы теории надежности информационных систем: Учебное пособие / С.А. Мартишин, В.Л. Симонов, М.В. Храпченко. - М.: ИД ФОРУМ: НИЦ ИНФРА-М, 2013. - 256 с.: ил.; 60x90 1/16. - (Высшее образование). (переплет) ISBN 978-5-8199-0563

2.2 Энтропия дискретного ансамбля сообщений. 8

2.4 Энтропия непрерывного ограниченного ансамбля. 12

2.3.2 Непрерывный канал передачи информации. 17

3.4 Теорема оптимального кодирования источника. 32

4.5 Теорема Шеннона о пропускной способности.