Построение кодов с заданной исправляющей способностью

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

Пусть известен объем алфавита источника N. Необходимое количество информационных символов определяется как наибольшее целое логарифма N:

,

Тогда N = 2 ^k.

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

Задача состоит в том, чтобы при заданных N и Е определить значность кода n, обладающего требуемыми корректирующими возможностями.

Полное число ошибочных комбинаций, подлежащих исправлению, равно Е · N = Е · 2 ^k. Так как количество запрещенных комбинаций равно N ₀ - N, то код обеспечивает исправление не более N ₀ - N комбинаций. Следовательно, необходимое условие для возможности исправления ошибок можно записать в виде:

Забиваем Сайты В ТОП КУВАЛДОЙ - Уникальные возможности от SeoHammer

Каждая ссылка анализируется по трем пакетам оценки: SEO, Трафик и SMM. SeoHammer делает продвижение сайта прозрачным и простым занятием. Ссылки, вечные ссылки, статьи, упоминания, пресс-релизы - используйте по максимуму потенциал SeoHammer для продвижения вашего сайта.

Что умеет делать SeoHammer

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

SeoHammer еще предоставляет технологию Буст, она ускоряет продвижение в десятки раз, а первые результаты появляются уже в течение первых 7 дней.

Зарегистрироваться и Начать продвижение

N · E £ N ₀ - N,

где N ₀=2 ⁿ – полное число кодовых комбинаций значностью n.

Далее получим:

Или

(17.1)

Формула (17.1) выражает условие для выбора значности кода n.

Рассмотрим частные случаи. Если имеются ошибки разной кратности, то прежде всего необходимо обеспечить устранение однократных ошибок t = 1:

.

В этом случае зависимость (17.1) примет вид:

или

При построении кода целесообразно пользоваться таблицей 3.

Таблица 3

Соотношение между k и n для t=1

 

k
n

 

Если необходимо обеспечить устранение всех ошибок кратности от 1 до t, то нужно учесть, что:

- число возможных однократных ошибок ,

- число возможных двукратных ошибок ,

- число возможных t -кратных ошибок ,

- общее число ошибок .

При этом зависимость (1.1) примет вид:

 

(17.2)

 

Откуда следует:

 

.

 

Пусть t = 2, тогда полное число ошибок Е равно:

 

Е = .

 

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

 

.

 

При построении кода можно воспользоваться таблицей 4.

 

Таблица 4

Соотношение между k и n для t =2

k
n

 

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

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

Сервис онлайн-записи на собственном Telegram-боте

Попробуйте сервис онлайн-записи VisitTime на основе вашего собственного Telegram-бота:
— Разгрузит мастера, специалиста или компанию;
— Позволит гибко управлять расписанием и загрузкой;
— Разошлет оповещения о новых услугах или акциях;
— Позволит принять оплату на карту/кошелек/счет;
— Позволит записываться на групповые и персональные посещения;
— Поможет получить от клиента отзывы о визите к вам;
— Включает в себя сервис чаевых.

Для новых пользователей первый месяц бесплатно.

Зарегистрироваться в сервисе

 

Лекция 18. Кодирование информации систематическим кодом.

План:

1. Систематические коды

2. Код Хемминга