Читать онлайн «Теория и практика кодов, контролирующих ошибки»

ТЕОРИЯ И ПРАКТИКА КОДОВ, КОНТРОЛИРУЮЩИХ ОШИБКИ THEORY AND PRACTICE OF ERROR CONTROL CODES RICHARD E. BLAHUT ADDISON-WESLEY PUBLISHING COMPANY READING, MASSACHUSETTS MENLO PARK, CALIFORNIA LONDON AMSTERDAM • DON MILLS, ONTARIO SYDNEY REPRINTED WITH CORRECTION 1984 Р. БЛЕЙХУТ ТЕОРИЯ И ПРАКТИКА КОДОВ, КОНТРОЛИРУЮЩИХ ОШИБКИ ПЕРЕВОД С АНГЛИЙСКОГО И. И. ГРУШКО и В. М. БЛИНОВСКОГО ПОД РЕДАКЦИЕЙ К. Ш. ЗИГАНГИРОВА МОСКВА „МИР" 1986 ББК 32. 811 Б68 УДК 519. 725 Блейхут Р. Б68 Теория и практика кодов, контролирующих ошибки: Пер. с англ. — М. : Мир, 1986. — 576 с, ил. Монография известного американского специалиста, адресованная тем, кто непосредственно разрабатывает программы и аппаратуру помехоустойчивого кодирования. В ней впервые излагается разработанный автором единый подход к кодированию и декодированию, основанный на дискретном преобразовании Фурье. Для чтения книги достаточно знать математику в объеме втузовских программ (первые главы содержат необходимые сведения по алгебре). Она может служить и основой для курсов лекций, и пособием при первоначальном ознакомлении с предметом. Для математиков-прикладников, программистов н инженеров, а также для аспирантов и студентов вузов. _ 1502000000-183 „ ос Б 041 (01)—86 2~86' Ч' ' ББК 32. 811 Редакция литературы по математическим наукам Copyright © 1983 by Addison-Wesley Publishing Company, Inc. © перевод на русский язык, «Мир», 1986 ОТ РЕДАКТОРА ПЕРЕВОДА Книга Р. Блейхута посвящена разделу науки, за которым традиционно закреплено название «теория кодов, исправляющих ошибки». В последнее время, однако, в зарубежной литературе все чаще используется более точный термин «коды, контролирующие ошибки», поскольку эта теория изучает не только исправление, но и обнаружение ошибок. В отличие от традиционных курсов теории кодирования, адресованных в первую очередь специалистам в области передачи информации, данная книга ориентирована на проектировщиков цифровых комплексов обработки данных независимо от того, для чего предназначены эти комплексы: для передачи данных, для их хранения или для других операций над ними. Это условие наложило свой отпечаток на структуру книги. В ней почти не рассматриваются вопросы оптимальности предлагаемых методов кодирования, а вопросы их схемной реализации исследуются более подробно, чем это обычно принято. Хотя книга в первую очередь адресована читателю с инженерным образованием и формально не требует от него предварительного знакомства с высшей алгеброй, ее математический уровень достаточно высок (отметим, что в начале книги имеются специальные главы, излагающие сведения из алгебры). Центральное место в книге занимает спектральная теория циклических кодов, в развитие которой автор внес существенный вклад. Достаточно отметить модификацию автором процедуры Бер- лекэмпа—Месси, позволившую сократить число операций декодирования с О (п2) до О (п log n). Эта теория излагается в гл. 8— 11 и частично в гл. 13 на основе дискретного преобразования Фурье (ДПФ) в конечных полях.