У. Питерсон - Коды, исправляющие ошибки (1267328), страница 3
Текст из файла (страница 3)
ошибки дара) Однако в реальной системе всегда есть случайные бки, и назначение кодов состоит в том, чтобы обнаруживать Фяг. $.2. Блок-схема типичной системы связи с яспольвопаппем копов, исправляющих ошябкя. и, быть может, исправлять такие ошибки. Эти коды не могут исправлять любую возможную комбинацию ошибок; они скорее предназначаются для того, чтобы исправлять наиболее правдоподобные комбинации ошибок. Ббльшая часть теории двоичных кодов основана на предположении, что каждый из символов искажается шумом независимо и что, следовательно, вероятность данной комбинации ошибок зависит только от числа ошибок. Так, например, разработаны коды, которые исправляют любую комбинацию из 1 или меньшего числа одиночных ошибок в блоке из п символов.
Хотя подобная схема может служить подходящей моде. лью для описания ошибок в некоторых каналах, в телефонных линиях связи илн в системах хранения информации на магнитной ленте, ошибки встречаются в основном пакетами. Время действия помех в телефонной линии связи, таких, например, как помехи, возникающие из-за молний или в режиме переключения, превышает продолжительность передачи одного символа. Далее, дефекты магнитной ленты занимают обычно больше места, чем требуется для записи одного символа. Следовательно, необходимы коды для исправления пакетов ошибок. Некоторые замечательные коды, которые будут рассмотрены в гл. 11 и 14„были разработаны специально для этих целей. Каналы связи, изображенные на фиг.
1.1 и 1.2, являются односторонними каналами. Очень часто в системах связи используются двусторонние каналы — факт, который должен быть учтен при построении кодов. В случае двустороннего канала можно, например, использовать код, обнаруживающий ошибки. Если на одном конце обнаружена ошибка, можно послать запрос на повторение передачи; это позволяет эффективно исправлять ошибки. Можно привести примеры односторонних каналов„в которых вероятность ошибки может быть уменьшена за счет использования кодов, исправляющих ошибки, а не за счет кодов, обнаруживающих ошибки, и повторной передачи.
Например, в случае хранения информации на магнитной ленте слишком поздно просить о повторной передаче после того, как лента уже хранилась неделю или месяц и ошибки обнаружились при чтении записи. Кодирование для кодов, исправляющих ошибки, ненамного сложнее, чем для кодов, обнаруживающих ошибки. Декодирование обычно требует сложного оборудования. При передаче, например, с космического корабля, когда размеры оборудования в передающей системе много важнее, чем размеры оборудования во всей системе связи, использование кодирующего оборудования для системы исправления ошибок окажется, вероятно, более практичным, чем использование системы повторной передачи с управлением на расстоянии. Сложная процедура исправления ошибок может произ- водиться на Земле, где ограничения, накладываемые на размеры оборудования, не являются столь жесткими.
В некоторых системах необходимо использовать коды, не требующие каналов обратной связи; такими кодами являются коды, исправляющие ошибки. С другой стороны, существует много причин для использования системы обнаружения ошибок и повторной передачи, если это возможно в реальных системах. Обнаружение ошибок по своей природе является задачей более простой, чем исправление ошибок, и требует поэтому более простого оборудования. Кроме того, обнаружение ошибок с повторной передачей представляет собой адаптивный процесс — передача избыточной информации возрастает, когда появляются ошибки. Это позволяет при определенных обстоятельствах добиваться для систем этого типа результатов, лучших, чем результаты, теоретически возможные для одностороннего канала.
Существуют определенные пределы для эффективности систем, в которых используется только простое обнаружение ошибок. Короткие коды не могут эффективно обнаруживать ошибки, тогда как использование чрезвычайно длинных кодов слишком часто приводит к повторной передаче. Можно показать, что, комбинируя исправление наиболее частых сочетаний ошибок и обнаружение с последующей повторной передачей для более редких сочетаний ошибок, можно превзойти эти пределы, и в действительности такая комбинация является зачастую более эффективной, чем либо только исправление ошибок, либо только обнаружение ошибок с повторной передачей.
Хотя в большей части современного оборудования используется только обнаружение ошибок с повторной передачей, было построено несколько систем, которые ясно продемонстрировали потенциальные возможности комбинированных методов исправления ошибок и обнаружения ошибок с обратной связью 137, 1791. 1.3. Типы кодов На вход кодера, изображенного на фнг. 1.2, поступает непреРывная последовательность информационных символов. На его выходе появляется другая последовательность, состоящая из не~~олько большего количества символов, которая подается на модулятор. Наоборот, на вход декодера поступает последовательность символов канала из демодулятора, которая преобразуется в несколько более короткую последовательность информационных сим~~~ов Правила, по которым действуют кодер и декодер, опреде.
лаются заранее выбранным определенным кодом. Существует два принципиально различных типа кодов. В кодере приспособленном для использования блоковых кодов, непре- рывная последовательность информационных символов разбивается на отрезки, содержащие по й символов, или блоки. В дальнейшем операции производятся над каждым блоком отдельно независимо от других в соответствии с выбранным кодом.
Каждому возможному информационному блоку сопоставляется набор из п символов канала, где и ) А. Этот набор, называемый кодовым еловом, передается по каналу связи, искажается шумом, а затем декодируется независимо от всех других кодовых слов. Величина и называется длиной кода или длиной блока. Прн использовании кодов другого типа, называемых древовидными кодами, информационная последовательность подвергается обработке без предварительного разбиения ее на независимые блоки.
В кодирующем устройстве этого типа информация обрабатывается непрерывно и каждой длинной (возможно, полубесконечпой) информационной последовательности сопоставляется кодовая последовательность, состоящая из несколько большего количества символов. В кодере последовательность, поступающая на его вход, разбивается на блоки нз й«символов, где йо — обычно небольшое число. Затем на основании этих А, символов и предшествующих информационных символов образуется блок длины пв из символов кодовой последовательности.
Название «древовидный код» основано на том, что правила кодирования для кодов этого типа удобнее всего описывать посредством древовидного графа. Этот вопрос рассматривается в равд. Кб. Из этих двух классов кодов теоретически значительно лучше поняты введенные первыми блоковые коды. Причина этого, повидимому, заключается в том, что блоковые коды оказались очень тесно связанными с уже известными ранее и относительно хорошо изученными математическими структурами. В связи с этим блоковым кодам посвящено больше исследований, чем древовидным. Сверточные коды являются частным случаем древовидных кодов.
Это очень важный класс кодов, поскольку из всех древовидных кодов сверточные коды являются наиболее простыми с точки зрения их реализации. В этой книге рассматриваются только сверточные древовидные коды. Что касается возможностей для исправления ошибок, то они почти одинаковы у блоковых и сверточных кодов, причем и те и другие коды подчиняются одним и тем же основным ограничениям. В частности, основная теорема Шеннона для дискретного канала с шумами справедлива для кодов обоих типов. Эта теорема состоит в том, что канал обладает явным образом определяемой пропускной способностью и что, используя соответствующие коды, можно передавать информацию с любой скоростью, не превосходящей пропускную способность канала, с произвольно малой вероятностью ошибочного декодирования.
1.4, Блоковые коды г!бозначим через д число различных символов, используемых при передаче по каналу; здесь д — произвольное число, хотя в последующих главах предполагается, что д является степенью простого числа и особое внимание уделяется двоичному случаю г,! = 2), Блоковым кодом называется совокупность М наборов длины и, составленных из символов канала. Этн и-ичные наборы длины и называются кодовыми словали. В этой книге, так же как во всех реальных системах и в большинстве теоретических исследований, число кодовых слов выбирается равным степени числа и, т. е. М=д".
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
