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

Оглавление

История кодирования, контролирующего ошибки 2

Приложения 5

Общие сведения о кодах и системах кодированной связи 7

Мешающие влияния в каналах связи 13

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

Пример. 21

Краткая классификация 23

Практика кодирования 31

Код Хэмминга 40

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

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

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

История кодирования, контролирующего ошибки

История кодирования, контролирующего  ошибки, началась в 1948 г. публикацией  знаменитой статьи Клода Шеннона. Шеннон показал, что с каждым каналом  связано измеряемое в битах в  секунду и называемое пропускной способностью канала число С, имеющее следующее значение. Если требуемая от системы связи скорость передачи информации R (измеряемая в битах в секунду) меньше С, то, используя коды, контролирующие ошибки, для данного канала можно построить такую систему связи, что вероятность ошибки на выходе будет сколь угодно мала. В самом деле, из шенноновской теории информации следует тот важный вывод, что построение слишком хороших каналов является расточительством; экономически выгоднее использовать кодирование. Фактически в работе Шеннона утверждается, что мощность сигнала, шум в канале и полоса частот ограничивают лишь скорость передачи, а не ее точность. Шеннон, однако, не указал, как найти подходящие коды, а лишь доказал их существование. В пятидесятые годы много усилий было потрачено на попытки построения в явном виде классов кодов, позволяющих получить обещанную сколь угодно малую вероятность ошибки, но результаты были скудными. В следующем десятилетии решению этой увлекательной задачи уделялось меньше внимания; вместо этого исследователи кодов предприняли длительную атаку по двум основным направлениям.

Первое направление носило чисто алгебраический характер и  преимущественно рассматривало  блоковые коды. Первые блоковые коды были введены в 1950 г., когда Хэмминг  описал класс блоковых кодов, исправляющих одиночные ошибки. Коды Хэмминга были разочаровывающе слабы по сравнению с обещанными Шенноном гораздо более сильными кодами. Несмотря на усиленные исследования, до конца пятидесятых годов не было построено лучшего класса кодов. В течение этого периода без какой-либо общей теории были найдены многие коды с малой длиной блока. Основной сдвиг произошел, когда Боуз и Рой-Чоудхури [1960] и Хоквингем [1959] нашли большой класс кодов, исправляющих кратные ошибки (коды БЧХ), а Рид и Соломон [1960] нашли связанный с кодами БЧХ класс кодов для недвоичных каналов. Хотя эти коды остаются среди наиболее важных классов кодов, общая теория блоковых кодов, контролирующих ошибки, с тех пор успешно развивалась.

Открытие кодов БЧХ  привело к поиску практических методов  построения жестких или мягких реализации кодеров и декодеров. Первый хороший  алгоритм был предложен Питерсоном. Впоследствии мощный алгоритм выполнения описанных Питерсоном вычислений был  предложен Берлекэмпом и Месси, и их реализация вошла в практику как только стала доступной новая цифровая техника. Второе направление исследований по кодированию носило скорее вероятностный характер. Ранние исследования были свя-заны с оценками вероятностей ошибки для лучших семейств блоковых кодов, несмотря на то, что эти лучшие коды не были известны. С этими исследованиями были связаны попытки понять кодирование и декодирование с вероятностной точки зрения, и эти попытки привели к появлению последовательного декодирования. В последовательном декодировании вводится класс неблоковых кодов бесконечной длины, которые можно описать деревом и декодировать с помощью алгоритмов поиска по дереву. Наиболее полезными древовидными кодами являются коды с тонкой структурой, известные под названием сверточных кодов. Эти коды можно генерировать с помощью цепей линейных регистров сдвига, выполняющих операцию свертки информационной последовательности. В конце 50-х годов для сверточных кодов были успешно разработаны алгоритмы последовательного декодирования. Интересно, что наиболее простой алгоритм декодирования - алгоритм Витерби - не был разработан для этих кодов до 1967 г. Применительно к сверточным кодам умеренной сложности алгоритм Витерби пользуется широкой популярностью, но для более мощных сверточных кодов он не практичен.

В 70-х годах эти два  направления исследований опять  стали переплетаться. Теорией сверточных кодов занялись алгебраисты, представившие ее в новом свете. В теории блоковых кодов за это время удалось приблизиться к кодам, обещанным Шенноном: были предложены две различные схемы кодирования (одна Юстесеном, а другая Гоппой), позволяющие строить семейства кодов, которые одновременно могут иметь очень большую длину блока и очень хорошие характеристики. Обе схемы, однако, имеют практические ограничения. Между тем к началу 80-х годов кодеры и декодеры начали появляться в конструкциях цифровых систем связи и цифровых систем памяти. 

ПРИЛОЖЕНИЯ

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

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

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

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

ОБЩИЕ СВЕДЕНИЯ О КОДАХ И СИСТЕМАХ КОДИРОВАННОЙ СВЯЗИ

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

Если сообщения обладают внутренними корреляционными связями, т. е. если одно сообщение некоторым  образом зависит от другого, как  это обычно бывает при передаче текстов  на естественных языках, то помехоустойчивость любого кода может быть повышена за счет статистических связей между сообщениями. Если эти связи слабые, или неизвестны, или их нельзя использовать для повышения  помехоустойчивости, то в этом случае форма представления сообщения  должна быть избыточной; в частности, число символов в коде сообщения  увеличивают, а между кодовыми символами  вводят искусственные корреляционные связи. Поэтому в некоторых случаях  помехоустойчивые коды называют избыточными. Введение избыточности в код позволяет  помимо обнаружения и исправления  ошибок повысить энергетическую эффективность  линии связи, обузить частотный  спектр передаваемого сигнала, сократить  время вхождения в связь путем  повышения помехозащищенности тракта синхронизации, улучшить корреляционные свойства ансамбля сигналов, простыми средствами реализовать разнесенный  прием. Вид помехоустойчивого кода зависит от структуры системы  связи, обобщенная схема которой  приведена на рис. 1.1. Всюду рассматриваем  системы связи, передающие только дискретные сообщения. В современных системах передачи дискретных сообщений последние  поступают на вход системы, как правило, от нескольких источников. Даже если внешний источник один, сама система связи содержит источник сигналов служебной связи, телеуправления и телесигнализации (ТУ-ТС). Скорость поступления сообщений от разных источников может быть как одинаковой, так и различной синхронной с собственной тактовой частотой аппаратуры связи или асинхронной с ней. Блок уплотнения (БУ) объединяет сообщения, поступающие от разных источников, в единую последовательность, как правило, двоичных символов с тактовой частотой, соответствующей скорости передачи системы связи. 
 
  
Рис. 1 — Схема системы связи:

ИИ - источник информации; БУ - блок уплотнения сообщений;КДШ, КДВ - кодеры внешний, внутренний; ПРШ, ПРВ - перемежители внешний, внутренний; М - модулятор; ПД - передатчик; ЛС - линия связи; ПР - приемник; Д - демодулятор; АЦП - аналого-цифровой преобразователь; БДС, БПС, БЛС - блоки додетекторного, последетекторного, логического сложения; ДПШ, ДПВ - деперемежители внешний, внутренний; ДКШ, ДКВ - декодер внешний, внутренний; БР-блок разуплотнения сообщений; ПИ-получатель информации; КОС - канал обратной связи.

Если скорости поступления  сообщений от источников асинхронны по отношению к собственной тактовой частоте системы связи, БУ осуществляет асинхронный ввод сообщений. Для  того чтобы при временном уплотнении различить сообщения на стороне  приема, БУ формирует маркер, обозначающий место первого источника в  общем цифровом потоке. Маркер повторяется  периодически, образуя сигнал цикловой синхронизации. Кодер вводит избыточность в передаваемый поток двоичных символов, причем кодирование сообщений в  зависимости от требуемой степени  повышения помехоустойчивости может  выполняться поэтапно и соответственно этапам различными кодерами. Первый после БУ кодер называют внешним (КДШ), последний - внутренним (КДВ). Сформированный кодером поток символов поступает в перемежитель. Во многих случаях ошибка в одном символе кода влечет за собой ошибки и в других смежных с ним символах той же последовательности, вызывая появление пакета ошибок на входе декодера, исправляющего ошибки. Если код рассчитан на исправление m ошибок на интервале из n смежных символов, а пакет ошибок вызывает больше чем m ложных символов, ошибка декодером не будет исправлена. Перемежитель разносит (во времени) смежные символы исходной кодовой последовательности более чем на n символов. При деперемежении на стороне приема разнесенные символы вновь собирают вместе; одновременно ошибки в пакете будут разнесены деперемежителем во времени более чем на n символов, и соответствующий деперемежителю декодер такие разнесенные ошибки сможет исправить.

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

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

Сложение сигналов в разнесенных  ветвях на стороне приема может производиться  как на входе демодулятора (додетекторное сложение), так и на его выходе (последетекторное сложение). В частности, если сигналы в ветвях некогерентны, последетекторное сложение называют квадратичным. Сравнительно недавно в системах связи с кодированными сигналами стали применять логическое объединение ветвей разнесения, реализующее последетекторный автовыбор ветви с наименьшим числом ошибок. Демодулятор (Д) производит оптимальную обработку элемента сигнала, заканчивающуюся обычно интегрированием со сбросом интегратора в определенный тактовый момент времени. Тем самым демодулятор дискретизирует во времени смесь огибающей сигнала с шумом. Формирование тактовых импульсов осуществляют устройства тактовой синхронизации, входящие в состав демодулятора. Аналого-цифровой преобразователь (АЦП) на выходе демодулятора дискретизирует (квантует) смесь огибающей сигнала с шумом по уровню. При квантовании на два уровня декодируется двоичный сигнал. Максимальное число уровней квантования, как правило, не превышает 16. Обычно число уровней равно 2, 4, 8 или 16. Декодер, работающий с двоичным сигналом, называют жестким, с недвоичным - мягким. Для работы декодера необходимы специфические (групповые) тактовые импульсы, формируемые в тракте групповой синхронизации, входящем в состав декодера. Назначение декодера состоит в уменьшении числа ошибок в сообщениях, выдаваемых системой связи, путем использования избыточности, заложенной в символьный поток кодером. Часть системы связи, включающая линию (радио- или проводную), называется каналом. Часть системы от выхода модулятора до входа АЦП образует канал передачи-приема сигнала, непрерывного по уровню (но дискретного по времени). Часть системы от выхода модулятора до выхода АЦП образует канал с входным сигналом, непрерывным по уровню и времени, и с выходным дискретным сигналом. От входа модулятора до выхода АЦП имеем дискретный (по времени и уровню) канал. В двунаправленной системе связи обычно создают канал обратной связи, по которому осуществляют управление работой системы.

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

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

Мешающие  влияния в каналах связи

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

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

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

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

Ретранслированная помеха создается в результате усиления и переизлучения переданного сигнала одной-двумя соседними станциями. Переизлученный и задержанный сигнал, попадая в приемник истинной станции, создает специфическую помеху, воздействующую тем сильнее, чем хуже корреляционные свойства передаваемых сигналов. Имитационная помеха (ИМП) близка по форме переданному сигналу; степень близости определяется числом передаваемых сигналов и их корреляционными свойствами. Часто ИМП называют также структурной или прицельной помехой. Название "прицельная помеха" становится оправданным при совпадении в приемнике фазы или средней частоты ИМП с фазой переданного сигнала или со средней частотой одного или нескольких частотных подканалов. В последнем случае помеху иногда называют сосредоточенной. В наземных радиолиниях причинами замираний, составляющих основную часть мешающих влияний естественного происхождения, служат многолучевость, метеоусловия, время года. Многолучевость вызывает быстрые замирания, метеоусловия и время года - медленные. Частотную селективность замираний определяют по снижению коэффициента частотной корреляции до значения 0,5 ... 0,6. Интервал частот, лежащий в пределах 1...0,5, называют полосой (интервалом) когерентности канала связи.

 Рис. 2 — Классификация мешающих влияний в линиях связи. 

Искажения сигнала  могут вызываться как характеристиками тракта передачи, так и помехами. Однако понятие искажения обычно связывают только с влиянием на сигнал линейных и нелинейных характеристик  тракта. Воздействие линейных характеристик, и в частности неравномерности  амплитудно-частотной характеристики (АЧХ), приводит к появлению межсимвольных  искажений (МСИ); ограничение амплитуды  сигнала вызывает появление нежелательных  частот в спектре, создающих помехи нелинейных переходов. Ошибки фиксируются  на выходе дискретного канала: именно они определяют верность информации. Деление ошибок на независимые и  пакетные вызвано главным образом  спецификой помехоустойчивого кода, его способностью исправлять или  обнаруживать ошибки.

Для априорной оценки эффективности  кода проводят имитационное моделирование, требующее знания статистического  распределения мешающих влияний. Обычно шум предполагают нормально распределенным (белым гауссовским шумом-БГШ). При большом разнообразии ИП нет, однако, единой универсальной модели, описывающей эти помехи. Как правило, уровни и длительности ИП принимают распределенными по экспоненциальному закону, а вероятность появления m импульсов на интервале времени Т_и.п (в соответствии с распределением Пуассона) P_и.п(m) = (LТ_и.п)^mехр(-LТ_и.п)/m!, где L-среднее число импульсов на интервале Т_и.п.

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

Для описания быстрых замираний  чаще всего применяют рэлеевское и райсовское распределения. Частотную селективность быстрых замираний описывают экспоненциальным распределением; функция частотной корреляции  R(f)=(ехр(-f/df0))²  или R(f)=exp(-f/df0),  
где df0 -интервал частотной корреляции. Общепринята аппроксимация медленных замираний логарифмически нормальным распределением.

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

• проводные линии связи - воздушные, магистральные кабельные (симметричные и коаксиальные), внутригородские кабельные, а также высоковольтные линии электропередач;
• радиотракты-радиорелейные прямой видимости (РРЛ), тропосферные (ТРЛ), космические (через ИСЗ и с дальними космическими кораблями), магистральные коротковолновые (KB) ЛС, а также линии радиосвязи с наземными подвижными объектами (РЛП);
• телефонные каналы различной протяженности, прямые и коммутируемые, организованные на ЛС различного типа;
• внутриаппаратные тракты магнитной записи-считывания и шины информационного обмена в ЭВМ. 
  

ОСНОВНЫЕ  ПРИНЦИПЫ ПОМЕХОУСТОЙЧИВОГО КОДИРОВАНИЯ

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

Рассмотрим вначале двоичный канал  связи с помехами, приводящими  к тому, что ошибки появляются независимо в каждом символе и средняя  вероятность ошибки равна Р=0,01. Если требуется рассмотреть произвольный блок из 10 символов на выходе канала, то весьма трудно выявить символы, которые являются ошибочными. Вместе с тем если считать, что такой блок содержит не более трех ошибок, то мы будем неправы лишь два раза на миллион блоков. Кроме того, вероятность, что мы окажемся правы, возрастает с увеличением длины блока. При увеличении длины блока доля ошибочных символов в блоке стремится к средней частоте ошибок в канале, а также, что очень важно, доля блоков, число ошибок в которых существенно отличается от этого среднего значения, становится очень малой. Простые вычисления помогают понять, насколько верным является это утверждение. Рассмотрев, например, тот же канал, вычислим вероятность того, что доля ошибочных символов превышает значение p, и построим график этой функции для нескольких значений длины блока.

Рис. 3 Вероятность того, что доля ошибочных символов e/N в блоке длиной N превышает р при вероятности Р e=0,01.

Кривые на рис. 1.3 показывают, что  при обработке символов блоками, а не одного за другим можно уменьшить  общую частоту ошибок. При этом потребуется, чтобы существовала схема  кодирования, нечувствительная к ошибкам  в некоторой доле символов блока  и не приводящая при этом к потере сообщением своей индивидуальности, т. е. не приводящая к ошибочному блоку. Из графиков на рис. 1.3 для различных  длин блоков видно, какую именно долю ошибок нужно исправлять, чтобы получить заданную вероятность ошибки блока. Он показывает также, что при фиксированной  вероятности ошибки блока доля ошибок, которые нужно исправлять, уменьшается  при возрастании длины блока. Сказанное свидетельствует о  резервах улучшения характеристик  при усреднении шума и о том, что  эти резервы возрастают при увеличении длины блока. Таким образом, длинные  блоковые коды эффективнее коротких. После того как установлена целесообразность исправления ошибок в символах, возникает следующий логичный вопрос: как это сделать? Ключ лежит в избыточности. После некоторых размышлений читатель поймет, что при исправлении ошибок в сообщении, представляемом последовательностью из n двоичных символов, очень важно учесть, чтобы не все 2ⁿ возможных последовательностей представляли сообщения. В самом деле, когда каждая из возможных принятых последовательностей n символов представляет некоторое сообщение, нет никаких оснований считать, что одна последовательность является более правильной, чем любая другая. Продолжая рассуждать таким же способом, можно ясно увидеть, что для исправления всех наборов из t или менее ошибок необходимо и достаточно, чтобы каждая последовательность, представляющая сообщение, отличалась от последовательности, представляющей любое другое сообщение, не менее чем в 2t+1 местах. Например, для исправления всех одиночных или всех двойных ошибок в символах нужно, чтобы каждые две последовательности, представляющие разные сообщения, отличались не менее чем в пяти символах. Каждая принятая последовательность, содержащая два ошибочных символа и, следовательно, отличающаяся от посланной последовательности ровно в двух местах, будет всегда отличаться от всех других последовательностей, представляющих сообщения, не менее чем в трех местах. Число позиций, в которых две последовательности отличаются друг от друга, будем называть расстоянием Хемминга d между этими двумя последовательностями. Наименьшее значение d для всех пар кодовых последовательностей называется кодовым расстоянием и обозначается d_min. Поскольку d_min всегда должно быть на единицу больше удвоенного числа исправляемых ошибок, можно написать t=[(d_min-l)/2], (1.1) где [ ] обозначает целую часть. Параметр t указывает, что все комбинации из t или менее ошибок в любой принятой последовательности могут быть исправлены. Имеются модели каналов, в которых значение t может быть больше указанного в (1.1). 

Пример.

Рассмотрим код, состоящий из четырех  кодовых слов 00000, 00111,11100 и 11011. Каждое кодовое слово используется для  представления одного из четырех возможных сообщений. Поскольку код включает лишь небольшую долю всех 32 возможных последовательностей из пяти символов, мы можем выбрать кодовые слова таким образом, чтобы каждые два из них отличались друг от друга не менее чем в трех позициях. Таким образом, кодовое расстояние равно трем и код может исправлять одиночную ошибку в любой позиции. Чтобы провести процедуру декодирования при этом коде, каждой из 28 недопустимых последовательностей нужно поставить в соответствие ближайшую к ней допустимую последовательность. Этот процесс ведет к созданию таблицы декодирования, которая строится следующим образом. Вначале под каждым кодовым словом выписываем все возможные последовательности, отличающиеся от него в одной позиции. В результате получаем часть табл. 1.2, заключенную между штриховыми линиями. Заметим, что после построения этой части осталось восемь последовательностей. Каждая из этих последовательностей отличается от каждого кодового слова не менее чем в двух позициях. Однако в отличие от других последовательностей эти восемь последовательностей нельзя однозначно разместить в таблице. Например, последовательностью можно поместить либо в первый, либо в четвертый столбец. При использовании этой таблицы в процессе декодирования нужно найти столбец, в котором содержится принятая последовательность, и а качестве выходной последовательности декодера взять кодовое слово, находящееся в верхней строке этого столбца. 

Таблица 2. Таблица декодирования для кода с четырьмя словами