Читать онлайн «Коды с малой плотностью проверок на четность»

m ιρ Ρ Галлагер . , ι Ι ΉΙβΙ" ι 4- ИЗДАТЕЛЬСТВО «МИР» LOW-DENSITY PARITY-CHECK CODES by Robert G. Gallager M. I. T. PRESS, CAMBRIDGE, MASSACHUSETTS 1963 БИБЛИОТЕКА СБОРНИКА „МАТЕМАТИКА" Р. Дж. ГАЛЛАГЕР КОДЫ С МАЛОЙ ПЛОТНОСТЬЮ ПРОВЕРОК НА ЧЕТНОСТЬ Перевод с английского А. ШЕВЕРДЯЕВА Под редакцией Р. Л. ДОБРУШИНА ИЗДАТЕЛЬСТВО «МИР» Москва 1966 У. Д. К. 621. 391. 015 Книга является монографией известного американского специалиста в области теории информации. Оиа посвящена практически важному классу алгебраических кодов и разработке легко реализуемых методов кодирования и декодирования для передачи информации по реальным каналам связи со скоростью, приближающейся к пропускной способности канала. Книга предназначена для научных работников и инженеров, занимающихся теорией информации и теорией кодирования, а также для математиков, интересующихся приложениями, и военных специалистов. Она доступна аспирантам и студентам старших курсов университетов, энергетических институтов и институтов связи. Редакция литературы по математическим наукам ПРЕДИСЛОВИЕ РЕДАКТОРА ПЕРЕВОДА Предлагаемая вниманию читателя книга Галла- гера является уже третьей в серии переведенных на русский язык небольших монографий по теории кодирования. Первая из этих монографий — книга Возен- крафта и Рейффена «Последовательное декодирование», вышедшая в русском переводе два года назад, хорошо известна читателям-специалистам. Вторая — книга Месси «Пороговое декодирование» — недавно издана в русском переводе. Объединяет эти три книги многое. Все они написаны молодыми учеными, принадлежащими к ведущей в США научной школе в области теории информации — школе, работающей в Массачусетсом технологическом институте, и все они представляют собой изложение оригинальных исследований их авторов, предложивших различные подходы к решению важнейшей проблемы техники связи: проблемы построения практически осуществимых методов кодирования и декодирования, позволяющих вести надежную передачу информации по реальным каналам связи со скоростью, приближающейся к теоретической границе — пропускной способности канала. Чтобы полностью исчерпать список основных идей в этой проблематике, нужно добавить к темам этих трех перечисленных книг, пожалуй, лишь широко изг вестный метод циклических кодов, хорошо изложенный в книге Питерсона «Коды, исправляющие ошибки». Кроме того, стоит специально отметить небольшую, но важную статью нашего соотечественника М. Пинскера, опубликованную в журнале «Проблемы передачи информации» (№ 1 за 1965 г. ), которая развеивает предрассудок (разделяемый, по-видимому, специалистами Массачусетской школы теории информации), состоящий в том, что возможность передачи информации со сколь угодно малой вероятностью ошибки и без чрезмерно большой по объему вычислительной работы при декодировании всегда* ограничена 6 Предисловие редактора перевода некоторой скоростью, меньшей пропускной способности канала. Метод Галлагера основан на простой, но остроумной математической идее.