Ћекции.ќрг


ѕоиск:




 атегории:

јстрономи€
Ѕиологи€
√еографи€
ƒругие €зыки
»нтернет
»нформатика
»стори€
 ультура
Ћитература
Ћогика
ћатематика
ћедицина
ћеханика
ќхрана труда
ѕедагогика
ѕолитика
ѕраво
ѕсихологи€
–елиги€
–иторика
—оциологи€
—порт
—троительство
“ехнологи€
“ранспорт
‘изика
‘илософи€
‘инансы
’ими€
Ёкологи€
Ёкономика
Ёлектроника

 

 

 

 


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




 

Ќа рис. 4.1 приведена упрощЄнна€ классификаци€ помехоустойчивых кодов [17]. ќстановимс€ кратко на основных особенност€х различных классов кодов. ѕомехоустойчивые (корректирующие) коды дел€тс€ на блочные и непрерывные.

 

 

 

–ис. 4.1

Ѕлочными называютс€ коды, в которых информационный поток символов разбиваетс€ на отрезки и каждый из них преобразуетс€ в определЄнную последовательность (блок) кодовых символов. ¬ блочных кодах кодирование при передаче (формирование проверочных элементов) и декодирование при приЄме (обнаружение и исправление ошибок) выполн€ютс€ в пределах каждой кодовой комбинации (блока) в отдельности по соответствующим алгоритмам. Ќепрерывные или рекуррентные коды образуют последовательность символов, не раздел€емую на отдельные кодовые комбинации.  одирование и декодирование непрерывно совершаютс€ над последовательностью элементов без делени€ их на блоки. ‘ормирование проверочных символов ведЄтс€ по рекуррентным (возвратным) правилам, поэтому непрерывные коды часто называют рекуррентными цепными.

¬ простейшем цепном коде каждый проверочный элемент формируетс€ путЄм сложени€ по модулю 2 соседних или отсто€щих друг от друга на определЄнное число позиций информационных элементов. ¬ канал св€зи передаЄтс€ последовательность импульсов, в которой за каждым информационным следует проверочный. ѕодобную чередующуюс€ последовательность разр€дов имеет, например, коррел€ционный манчестерский код.

  непрерывным кодам относ€тс€ и свЄрточные коды, в которых каждый информационный символ, поступающий на вход кодирующего устройства, вызывает по€вление на его выходе р€да проверочных элементов, образованных суммированием по модулю 2 данного символа и k-1 предыдущих информационных символов. –екуррентные коды позвол€ют исправл€ть групповые ошибки (Ђпачкиї) в каналах св€зи.

Ѕлочные коды дел€тс€ на равномерные и неравномерные. ¬ равномерных кодах, в отличие от неравномерных, все кодовые комбинации содержат одинаковое число n -символов (разр€дов) с посто€нной длительностью τ0 импульсов символов кода. –авномерные коды, в основном, и примен€ютс€ в системах св€зи, так как это упрощает технику передачи и приЄма.

 лассическими примерами неравномерного кода €вл€ютс€: код ћорзе, широко примен€емый в телеграфии, и код ’афмена, примен€емый дл€ компрессии информации (факсимильна€ св€зь, Ё¬ћ).

Ќикаких специальных мер по исправлению и обнаружению ошибок в коде ћорзе не предусматриваетс€ в св€зи с большой избыточностью самого передаваемого текста. ¬ этом смысле, код ћорзе не относитс€ к классу корректирующих кодов.

ѕочти все блочные корректирующие коды принадлежат к разделимым кодам, в которых кодовые комбинации состо€т из двух частей: информационной и проверочной. »х символы всегда занимают одни и те же позиции, т. е. располагаютс€ на определенных местах.  ак правило, в таких кодах, все кодовые комбинации которых содержат n символов, первые k символов €вл€ютс€ информационными, а за ними располагаютс€ (n-k) проверочных символов. ¬ соответствии с этим разделимые коды получили условное обозначение Ц (n-k)-коды.

¬ неразделимых кодах деление на информационные и проверочные символы отсутствует.   таким кодам относ€тс€, в частности, коды с посто€нным весом, так называемые равновесные коды. Ќапример, ћеждународным консультативным комитетом по телеграфии и телефонам (ћ  ““) рекомендован дл€ использовани€ телеграфный код є 3 Ц семиразр€дный код с посто€нным весом, т. е. с числом единиц в каждой кодовой комбинации, равным 3 (W = 3).

—истематические коды образуют наиболее обширную группу (n, k)-разделимых кодов. ќсобенностью этих кодов €вл€етс€ то, что проверочные (корректирующие) символы образуютс€ с помощью линейных операций над информационными.  роме того, люба€ разрешЄнна€ кодова€ комбинаци€ может быть получена в результате линейной операции над набором k линейно независимых кодовых комбинаций. ¬ частности, суммирование по модулю 2 двух и более разрешЄнных комбинаций также дает разрешЄнную кодовую комбинацию. ѕоскольку теоретической основой получени€ таких комбинаций €вл€етс€ математический аппарат линейной алгебры, то коды и называют линейными,
а учитыва€, что проверочные символы формируютс€ по определЄнной системе (правилам), блочные равномерные разделимые линейные коды получили название систематических. »спользование аппарата линейной алгебры, в которой важное значение имеет пон€тие Ђгруппаї, породило и другое название этих кодов Ц групповые.

Ёти коды получили наибольшее применение в системах передачи дискретной информации.

Ќесистематические (нелинейные) коды указанными выше свойствами не обладают и примен€ютс€ значительно реже, в специальных случа€х. ѕримером нелинейного кода €вл€етс€ уже упоминавшийс€ неразделимый, равновесный код. Ёти коды обычно используютс€ в несимметричных каналах св€зи, в которых веро€тность перехода 1 в 0 значительно больше веро€тности перехода 0 в 1, или наоборот. ¬ таких каналах очень маловеро€тно, чтобы в одном блоке были переходы обоих видов, и поэтому почти все ошибки привод€т к изменению веса блока и, следовательно, обнаруживаютс€.

ƒругим примером несистематического кода €вл€етс€ код с контрольным суммированием Ц итеративный код. ¬ этом коде проверочные разр€ды формируютс€ в результате суммировани€ значений разр€дов, как в данной кодовой комбинации, так и одноимЄнных разр€дов в р€де соседних с ней комбинаций, образующих совместный блок. »теративные коды позвол€ют получить так называемые мощные коды, т. е. коды с длинными блоками и большим кодовым рассто€нием при сравнительно простой процедуре декодировани€. »теративные коды могут строитьс€ как комбинационные, посредством произведени€ двух или более систематических кодов.

  комбинационным кодам можно отнести также антифединговые коды, предназначенные дл€ обнаружени€ и исправлени€ ошибок в каналах с замирани€ми (федингом) сигналов. ƒл€ таких каналов с группированием ошибок примен€ют метод перемежени€ символов или декоррел€ции ошибок. ќн заключаетс€ в том, что символы, вход€щие в одну кодовую комбинацию, передаютс€ не непосредственно друг за другом, а перемежаютс€ символами других кодовых комбинаций исходного систематического или любого другого кода. ≈сли интервал между символами, вход€щими в одну кодовую комбинацию, сделать длиннее Ђпам€тиї (интервала коррел€ции) канала с замирани€ми, то в пределах длительности одной исходной кодовой комбинации группировани€ ошибок не будет. Ќа приЄме после обратной Ђрасфасовкиї в кодовых комбинаци€х можно производить декодирование с обнаружением и исправлением ошибок.

¬ систематических кодах различают два метода формировани€ проверочной группы символов: поэлементный и в целом.

Ќаиболее известны среди систематических кодов коды ’емминга, которые исторически были найдены раньше многих других кодов и сыграли большую роль в развитии теории корректирующих кодов. ¬ этих кодах используетс€ принцип проверки на чЄтность определЄнного р€да информационных символов. ѕроверочна€ группа из r символов формируетс€ поэлементно по соответствующему алгоритму.  оды ’емминга, имеющие dmin = 3, позвол€ют исправить одну ошибку.

–асширенные коды ’емминга стро€тс€ в результате дополнени€ кодов
с dmin = 3 общей проверкой каждой из кодовых комбинаций на чЄтность, т. е. ещЄ одним проверочным символом. Ёто позвол€ет увеличить минимальное кодовое рассто€ние до dmin = 4.

÷иклические коды также относ€тс€ к классу линейных систематических кодов и обладают всеми их свойствами.  оды названы циклическими потому, что циклический сдвиг любой разрешЄнной кодовой комбинации также €вл€етс€ разрешЄнной комбинацией. “еори€ построени€ циклических кодов базируетс€ на разделах высшей алгебры, изучающей свойства двоичных многочленов. ќсобую роль в этой теории играют так называемые неприводимые многочлены, т. е. полиномы, которые не могут быть представлены в виде произведени€ многочленов низших степеней. ¬ св€зи с этим, циклические коды относ€т к разновидности полиномиальных кодов.

—реди циклических кодов особое место занимает класс кодов, предложенных Ѕоузом и –ой-„оудхури и независимо от них Ц ’оквингемом.  оды Ѕоуза Ц „оудхури Ц ’оквингема, Ѕ„’-коды отличаютс€ специальным выбором порождающего (образующего) циклический код полинома, что приводит к простой процедуре декодировани€.

¬ циклических кодах r проверочных символов, добавл€емых к исходным k информационным, могут быть получены сразу, т. е. в целом, в результате умножени€ исходной подлежащей передаче кодовой комбинации Q(x) простого кода на одночлен xr и добавлением к этому произведению остатка R(x), полученного в результате делени€ произведени€ на порождающий полином –(х).

ќтметим, что коды ’емминга также можно получить по алгоритмам формировани€ циклических кодов.

ѕроблема помехоустойчивого кодировани€ представл€ет собой обширную область теоретических и прикладных исследований. ќсновными задачами при этом €вл€ютс€ следующие: отыскание кодов, эффективно исправл€ющих ошибки требуемого вида; нахождение методов кодировани€ и декодировани€
и простых способов их реализации.

Ќаиболее разработаны эти задачи применительно к систематическим кодам. “акие коды успешно примен€ютс€ в вычислительной технике, различных автоматизированных цифровых устройствах и цифровых системах передачи информации.

 





ѕоделитьс€ с друзь€ми:


ƒата добавлени€: 2015-05-08; ћы поможем в написании ваших работ!; просмотров: 1204 | Ќарушение авторских прав


ѕоиск на сайте:

Ћучшие изречени€:

Ћибо вы управл€ете вашим днем, либо день управл€ет вами. © ƒжим –он
==> читать все изречени€...

2080 - | 1820 -


© 2015-2024 lektsii.org -  онтакты - ѕоследнее добавление

√ен: 0.009 с.