Пред.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 След.
Макеты страниц
Распознанный текст, спецсимволы и формулы могут содержать ошибки, поэтому с корректным вариантом рекомендуем ознакомиться на отсканированных изображениях учебника выше Также, советуем воспользоваться поиском по сайту, мы уверены, что вы сможете найти больше информации по нужной Вам тематике ДЛЯ СТУДЕНТОВ И ШКОЛЬНИКОВ ЕСТЬ
ZADANIA.TO
ПРЕДИСЛОВИЕ РЕДАКТОРА ПЕРЕВОДАОсновным препятствием на пути широкого практического применения кодов, исправляющих любые сочетания ошибок кратности В ряде случаев эта сложность связана с тем, что число операций (или, что одно и то же, объем памяти), которое требуется выполнить при декодировании, экспоненциально увеличивается с ростом Именно поэтому в последнее время внимание многих исследователей обращено на разработку методов декодирования, допускающих автоматизацию с помощью реально осуществимого (по объему и быстродействию) оборудования. Таким образом, задача построения оптимальных и близких к ним кодов вытесняется задачей построения кодов с простым алгоритмом декодирования, обеспечивающих вместе с тем достаточно хорошее использование избыточности. Одним из наиболее перспективных в этом отношении является весьма интенсивно развиваемое направление, известное в литературе по теории кодирования как последовательное декодирование. Разработанное впервые Возенкрафтом и Рейффеном и усовершенствованное в дальнейшем другими авторами последовательное декодирование является асимптотически оптимальным (в смысле Шеннона), причем число операций, необходимое в среднем для декодирования одного символа, пропорционально величине Ортогональные проверки и идея их использования состоят в следующем. Предположим, что для каждого символа
при условии, что
а равенство Добавим к разделенным проверкам (1) тривиальное соотношение
и при декодировании будем определять символ а, из подставляются принятые кодовые символы (некоторые из них искажены помехами). Из свойств ортогональных проверок следует, что искажение Таким образом, при наличии Для линейных кодов соотношения (1) являются линейными [над полем Впервые мажоритарное декодирование было использовано для декодирования кодов Рида — Маллера. Однако этот метод не нашел широкого практического применения, поскольку для каждого символа кода необходимо реализовать свою систему ортогональных проверок. Широкие перспективы перед мажоритарным декодированием открылись только тогда, когда была показана возможность его применения к некоторым классам блоковых циклических и сверточных непрерывных кодов. Для этих кодов при сдвиге (в случае блоковых кодов — циклическом) система ортогональных проверок для символа Существенным достоинством мажоритарного декодирования является также и то, что, кроме всех ошибок кратности Кроме того, при незначительном изменении мажоритарного устройства можно часть корректирующей способности кода использовать для обнаружения (а не только для исправления) ошибок или наряду с ошибками исправлять также и стирания кодовых символов. Вместе с тем необходимо отметить, что все известные коды, допускающие мажоритарное декодирование (как блоковые циклические, так и сверточные непрерывные), не являются асимптотически оптимальными, т. е. при фиксированной скорости передачи вероятность ошибки не может быть сделана сколь угодно малой (за счет увеличения Однако при сравнительно большом Большая часть книги Месси посвящена подробному описанию, построению и исследованию сверточных непрерывных кодов, допускающих мажоритарное декодирование. В ней приводятся оценки, характеризующие качество таких кодов, и рассматриваются различные методы их построения. Одним из главных недостатков многих методов декодирования непрерывных кодов является эффект так называемого «размножения» ошибок. Автор уделяет ему достаточно внимания и указывает некоторые меры борьбы с этим недостатком. Весьма важным и интересным является предложенное автором обобщение мажоритарного декодирования, при котором символ причем весовые множители зависят от статистики ошибок. Применение вероятностных критериев, достаточно просто реализуемых при использовании ортогональных проверок, позволяет более полно использовать статистические свойства канала. Последнее особенно важно для каналов с переменными параметрами. Для двоичного кода реализация указанного метода, равно как и мажоритарного декодирования, сводится к использованию некоторого порогового устройства. Поэтому автор использовал общее название порогового декодирования как для обоих этих методов, так и для всей книги. Две главы книги Месси посвящены описанию мажоритарного (или порогового) декодирования применительно к блоковым кодам. В отличие от непрерывных кодов, исследование которых отличается исключительной полнотой и содержит много интересных и важных результатов, блоковые коды исследованы в книге Месси значительно менее подробно. Однако и для блоковых кодов автор получил важные результаты. Во-первых, ему удалось показать возможность построения систем мажоритарных проверок, полностью реализующих кодовое расстояние, не для отдельных конкретных кодов, а для целого класса — кодов максимальной длины. Во-вторых, введенный автором процесс ортогонализации в L шагов представляет принципиальное обобщение метода мажоритарного декодирования применительно к блоковым кодам. Этот вопрос не нашел сколько-нибудь полного разрешения в книге Месси, но можно ожидать, что дальнейшие исследования в этом направлении существенно расширят класс блоковых кодов, к которым можно будет применить методы мажоритарного декодирования. Месси не рассматривал методов построения блоковых кодов, допускающих мажоритарное декодирование. Единственные результаты в этом направлении получены в Советском Союзе В. Д. Колесником и Е. Т. Мирончиковым. Они изложены в диссертациях авторов и их совместной статье «Некоторые циклические коды и схема декодирования по большинству проверок». Предложенные достаточно общие методы построения блоковых циклических кодов, допускающих мажоритарное декодирование, использованы для построения большого числа конкретных кодов. Системы разделенных проверок для сумм некоторых символов, являющиеся основой ортогонализации в L шагов, также рассмотрены Мирончиковым и Колесником при совершенно ином подходе к решению задачи. Авторы указали некоторые способы построения кодов, для которых существуют такие системы проверок. Наконец, введенные ими «связанные» проверки совершенно не рассмотрены Месси. Таким образом, книга Месси и работы Колесника и Мирончикова чрезвычайно удачно дополняют друг друга и в совокупности позволяют составить достаточно полное представление о современном состоянии и основной проблематике теории мажоритарного декодирования. Учитывая незавершенность теории мажоритарного декодирования и важность дальнейших исследований в этой области, можно с полным основанием утверждать, что книга Месси, знакомящая читателей с основными идеями этой теории, несомненно, будет полезной инженерам, аспирантам и научным работникам, занимающимся кодами, исправляющими ошибки. Э. Л. Блох ПРЕДИСЛОВИЕ АВТОРАСпециалисты по теории информации чувствуют все большую ответственность за то, что их наука, несомненно интересная и важная, пока еще внесла столь незначительные изменения в существующие методы передачи сообщений. Действительно, после пятнадцати лет бурной исследовательской деятельности было бы вполне естественно ожидать какого-нибудь практического приложения метода исправления ошибок. Инженерам-связистам, которые заинтересованы в ликвидации разрыва между теорией и практикой кодирования, главным образом и адресована эта монография. Пороговое декодирование представляет собой метод исправления ошибок, особенно удобный для технической реализации. Для того чтобы подчеркнуть техническую точку зрения, мы уделяем значительное внимание вопросам создания простых логических схем, осуществляющих исправление ошибок. Мы надеемся, что эта книга будет стимулировать развитие других практических методов декодирования, обязательной чертой которых явится невысокая стоимость оборудования на передающем и приемном концах. (С удовлетворением отмечаем, что корпорация «Кодекс» уже изготовила кодирующее и декодирующее устройство, основанное на принципах порогового декодирования.) Расположение материала позволяет облегчить переход от теории к практике. Идеи порогового декодирования сформулированы главным образом в гл. I. В гл. II описываются сверточные коды, а три следующие главы посвящены специальным сверточным кодам для порогового декодирования, схемам декодирования и характеристикам декодирования. Гл. VI и VII посвящены приложению порогового декодирования к блоковым кодам. От читателя не требуется никакой специальной подготовки: предполагается лишь общее знакомство с теорией вероятностей. Там, где используются алгебраические сведения (а их в книге немного), они всюду поясняются. Вообще, алгебраический подход используется только там, где он углубляет понимание рассматриваемых понятий; там же, где можно обойтись без алгебраических методов, используются другие средства: например, линейные коды трактуются на основе теории линейных уравнений, а не теории групп. Считается, что книга Питерсона «Коды, исправляющие ошибки» должна быть знакома любому серьезному работнику в области методов кодирования. К этой книге мы отсылаем читателя всякий раз, когда это оказывается полезным. Для дальнейшего чтения автор предложил бы книгу Фано «Передача информации», которая во всей полноте излагает развитие основ теории информации, и важную монографию Возенкрафта и Рейффена «Последовательное декодирование», в которой сверточные коды рассматриваются с иной точки зрения, чем принятая в нашей книге. Основой этой монографии является докторская диссертация автора, написанная под руководством профессора Массачусетского технологического института Дж. М. Возенкрафта. Вполне понятна моя большая благодарность профессору Возенкрафту. Далее я обязан профессорам Массачусетского технологического института П. Элайесу, Р. Г. Галлагеру и К. Э. Шеннону за их щедрую помощь новичку в теории информации. Это исследование оказалось возможным благодаря частичной поддержке исследовательской лаборатории электроники Массачусетского технологического института, которая в свою очередь финансируется армией США, научно-исследовательским отделом ВВС и исследовательским отделом ВМФ. Я также хочу выразить признательность за помощь, оказанную издательством и вычислительным центром Массачусетского технологического института и Ассоциацией национального научного фонда США (1959—1962). Я не называю многих имен тех, кто так или иначе способствовал написанию этой монографии, однако я не могу не назвать моей жены Кэтрин Крампер Месси. Джеймс Л. Месси Нотр-Дам, Индиана, 27 апреля 1963 г.
|
1 |
Оглавление
|