У. Питерсон - Коды, исправляющие ошибки (1267328), страница 2

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 2)

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

Она может быть использована как учебник для подготовки специалистов математического и инженерного профиля. Перевод выполнен Л. Е. Филипповой (гл. 1 — 8 и приложения), И. М. Бояриновым (гл. 9, равд. 9.4 — 9.8; гл. 10) и И. Н. Дынькиным (гл. 9, равд.

9.1 — 9.3; гл. 1! — 15). Р. Добрушин, С Самойленко Предисловие авторов Со времени опубликования первого издания этой книги в теории кодирования произошли значительные сдвиги, и коды, исправляющие ошибки, нашли применение в многочисленных системах передачи и хранения информации. Необходимость пересмотра первого издания возникла по меньшей мере пять лет назад. Однако с момента опубликования первого издания было напечатано так много новых работ по теории кодов, исправляющих ошибки, что подготовка второго издания оказалась практически значительно более трудной задачей, чем написание оригинальной монографии.

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

Основные из этих работ включены в книгу В. Д. Колесника и Е. Т. Мирончикова «Декодирование циклических кодов» (1968), заслуживающую самой высокой оценки, Значительная часть этой книги посвящена мажоритарному декодированию. В превосходной книге С. И. Самойленко «Помехоустойчивое кодирование» (1966) особое внимание уделяется кодам, исправление ошибок в которых легко осуществляется посредством вычислительных машин.

Известны также монографии 1О. Г. Дадаева «Арифметические коды, исправляющие ошибки» (1969) и Л. Ф. Бородина «Введение в теорию помехоУстойчивого кодирования» (1968). В последней описываются некоторые методы декодирования, основанные на использовании аналоговых сигналов на выходе. Показателем размаха работ в СССР по этим вопросам является также обширная библиография «Обзор новых результатов по теории кодирования в Советском Союзе»,составленная Каутцем и Левиттом (1ЕЕЕ Тгапз., 1Т-15, № 1, Р1.

11), которой упоминается свыше четырехсот работ по теории кодирования. В связи с этим, быть может, самым подходящим для данной книги явилось бы название «Коды, исправляющие ошибки, в Западном мире». Второе издание по существу содержит весь материал первого издания. Наиболее значительные добавления — гл. 10, в которой описываются мажоритарные коды, гл. 12 о синхронизации и гл. 13 и 14, посвященные сверточным кодам. Много нового материала включено в гл. 5 и 8. Мы рады возможности поблагодарить коллегу по Гавайскому университету Шу Линя за многие полезные замечания и обсуждение, продолжавшееся в течение четырех лет, которые понадобились для написания этой книги. Значительный вклад в данную работу сделали также Касами, Чен и Берлекэмп.

Отдельные главы в книге связаны следующим образом: 1, 2, 3(1, 2), 4(3), 5(3), 6(2), 7(6), 8(3, 7), 9(8), 10(8), 11(8), 12(8), 13(3), 14(3), 15(6). У. Питерсов, И. Дк. Увиден мл. 1 Проблема кодирования В течение последних двух десятилетий несколько важных до. стижений стимулировали быстрое развитие кодов, исправляющих ошибки, То внешнее для теории кодирования обстоятельство, что стоимость электронных устройств на интегральных схемах в последние годы убывала почти со столь же драматической скоростью, как и их размеры, ускорило развитие цифровой вычислительной техники и периферийных устройств вычислительных машин, что а свою очередь привело к драматическому росту количества данных, передаваемых от одной машины к другой. Недопустимость ошибок а вычислительных системах, а в некоторых случаях и критическая природа самих данных требовали использования оборудования, исключающего ошибки, или какого-либо рода кодов, исправляющих или обнаруживающих ошибки на выходе конечных устройств.

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

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

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

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

Заметим, что кодер включает в себя устройство, которое обычно называют модулятором, а в декодер входит устройство, которое обычно называют детектором. Анализ показывает, что в большинстве случаев каналы связи, описываемые схемой, представленной на фиг. 1.1, обладают определенной пропускной способностью для передачи информации. Более того, если скорость создания информации источником сообщения меньше пропускной способности канала, то можно выбрать совокупность сигналов так, чтобы вероятность ошибочного декодирования была произвольно малой 179, 81, 173, 270.

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

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

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

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

Характеристики

Список файлов книги