Главная страница Случайная страница
Разделы сайта
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
Построение кодов с заданной исправляющей способностью
|
|
До сих пор при рассмотрении корректирующих кодов мы предполагали заданной его значность n. Повышение корректирующей способности кода достигалось при сохранении n за счет уменьшения множества N разрешенных комбинаций (или уменьшения количества k информационных символов). Обычно же на практике коды строятся в обратном порядке: вначале выбирается количество информационных символов k, исходя из объема алфавита источника, а затем обеспечивается необходимая корректирующая способность кода за счет добавления избыточных символов.
Пусть известен объем алфавита источника N. Необходимое количество информационных символов определяется как наибольшее целое логарифма N:
,
Тогда N = 2 k.
Пусть также известно полное число ошибок Е, которое необходимо исправить.
Задача состоит в том, чтобы при заданных N и Е определить значность кода n, обладающего требуемыми корректирующими возможностями.
Полное число ошибочных комбинаций, подлежащих исправлению, равно Е · N = Е · 2 k. Так как количество запрещенных комбинаций равно N 0 - N, то код обеспечивает исправление не более N 0 - N комбинаций. Следовательно, необходимое условие для возможности исправления ошибок можно записать в виде:
N · E £ N 0 - N,
где N 0=2 n – полное число кодовых комбинаций значностью n.
Далее получим:
| N 0 ³ (1+ E) · N |
Или
| (17.1) |
Формула (17.1) выражает условие для выбора значности кода n.
Рассмотрим частные случаи. Если имеются ошибки разной кратности, то прежде всего необходимо обеспечить устранение однократных ошибок t = 1:
.
В этом случае зависимость (17.1) примет вид:
| ||
или
При построении кода целесообразно пользоваться таблицей 3.
Таблица 3
Соотношение между k и n для t=1
| k | ||||||
| n |
Если необходимо обеспечить устранение всех ошибок кратности от 1 до t, то нужно учесть, что:
— Регулярная проверка качества ссылок по более чем 100 показателям и ежедневный пересчет показателей качества проекта.
— Все известные форматы ссылок: арендные ссылки, вечные ссылки, публикации (упоминания, мнения, отзывы, статьи, пресс-релизы).
— SeoHammer покажет, где рост или падение, а также запросы, на которые нужно обратить внимание.
SeoHammer еще предоставляет технологию Буст, она ускоряет продвижение в десятки раз, а первые результаты появляются уже в течение первых 7 дней. Зарегистрироваться и Начать продвижение
- число возможных однократных ошибок 
,
- число возможных двукратных ошибок 
,
- число возможных t -кратных ошибок 
,
- общее число ошибок 
.
При этом зависимость (1.1) примет вид:
| (17.2) |
Откуда следует:
.
Пусть t = 2, тогда полное число ошибок Е равно:
Е = 
.
Длину кодовых комбинаций можно определить из следующего соотношения:
.
При построении кода можно воспользоваться таблицей 4.
Таблица 4
Соотношение между k и n для t =2
| k | ||||
| n |
Условие (17.2) является нижней оценкой для длины корректирующего кода, т. е. оно определяет необходимую минимальную длину кода n, обеспечивающую исправление ошибок заданной кратности при известном числе разрешенных комбинаций N или числе информационных символов k.
Это же условие является верхней оценкой для N или k, т. е. определяет максимально возможное число разрешенных комбинаций или информационных символов для кода длины n, обеспечивающего исправление ошибок заданной кратности.
Лекция 18. Кодирование информации систематическим кодом.
План:
1. Систематические коды
2. Код Хемминга
|
|