телекоммуникации теория кодирования информации теория кодов
Размер
4.7 МБ
СКАЧАТЬ КНИГУ
ЧИТАТЬ ONLINE
БУМАЖНАЯ ВЕРСИЯ КНИГИ
Монография известного американского специалиста, адресованная тем, кто непосредственно разрабатывает программы и аппаратуру помехоустойчивого кодирования. В ней впервые излагается разработанный автором единый подход к кодированию к декодированию, основанный на дискретном преобразовании Фурье.
Для чтения книги достаточно знать математику в объеме вузовской программы (первые главы содержат необходимые сведения по алгебре). Она может служить и основой для курсов лекция, и пособием при первоначальном ознакомлении с предметом.
Для математиков-прикладников, программистов к инженеров, а также для аспирантов и студентов вузов.
Читать онлайн «Теория и практика кодов, контролирующих ошибки»
Автор Блэйхут Р.(Blahut)
ТЕОРИЯ И ПРАКТИКА КОДОВ, КОНТРОЛИРУЮЩИХ ОШИБКИ
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
ОТ РЕДАКТОРА ПЕРЕВОДА Книга Р. Блейхута посвящена разделу науки, за которым традиционно закреплено название «теория кодов, исправляющих ошибки». В последнее время, однако, в зарубежной литературе все чаще используется более точный термин «коды, контролирующие ошибки», поскольку эта теория изучает не только исправление, но и обнаружение ошибок. В отличие от традиционных курсов теории кодирования, адресованных в первую очередь специалистам в области передачи информации, данная книга ориентирована на проектировщиков цифровых комплексов обработки данных независимо от того, для чего предназначены эти комплексы: для передачи данных, для их хранения или для других операций над ними. Это условие наложило свой отпечаток на структуру книги. В ней почти не рассматриваются вопросы оптимальности предлагаемых методов кодирования, а вопросы их схемной реализации исследуются более подробно, чем это обычно принято. Хотя книга в первую очередь адресована читателю с инженерным образованием и формально не требует от него предварительного знакомства с высшей алгеброй, ее математический уровень достаточно высок (отметим, что в начале книги имеются специальные главы, излагающие сведения из алгебры). Центральное место в книге занимает спектральная теория циклических кодов, в развитие которой автор внес существенный вклад. Достаточно отметить модификацию автором процедуры Бер- лекэмпа—Месси, позволившую сократить число операций декодирования с О (п2) до О (п log n). Эта теория излагается в гл. 8— 11 и частично в гл. 13 на основе дискретного преобразования Фурье (ДПФ) в конечных полях. Хотя связь ДПФ с циклическими кодами была известна и ранее, Р. Блейхут был первым, кто заметил большие потенциальные возможности такого подхода. Этот подход не только позволяет упростить процедуру декодирования, но и способствует более глубокому пониманию теории циклических кодов. В основном книга посвящена теории блоковых кодов, и автор излагает ее превосходно.
. Теория сверточных кодов излагается
б ОТ РЕДАКТОРА ПЕРЕВОДА несколько бегло и не всегда достаточно четко. В частности, минимальное расстояние ‘сверточных^кодов, введенное в гл. 12, мало связано с реальными характеристиками этих кодов, а их теоретическое описание неточно. Некоторые неточности содержит и гл. 15, посвященная связи модуляции и кодирования. В списке литературы неполно отражен вклад в теорию кодирования советских ученых, так что в отдельных случаях переводчики (гл. 1, 2, 4—6 и 8—15 переведены И. И. Грушко, гл. 3 и 7 — В. М. Блиновским) сочли необходимым дать соответствующие комментарии. При переводе учтены исправления, внесенные автором в первоначальный вариант книги, и исправлены замеченные опечатки. Переводчики и редактор выражают признательность автору книги за сотрудничество в процессе перевода книги, в частности за любезно присланное им исправленное ее издание. Соответствующие изменения внесены в перевод в корректуре. К- Ш. Зигангиров
ПРЕДИСЛОВИЕ К РУССКОМУ ИЗДАНИЮ Автор переведенной на иностранный язык книги чувствует себя как отец, сын которого покидает дом, чтобы начать собственную жизнь: к чувству гордости примешивается сознание, что книга начинает новую жизнь, которую ты никогда не узнаешь. Русское издание готовилось специалистами высокого класса: редактором Камилем Зигангировым и переводчиками Инной Гру- шко и Владимиром Блиновским. Я очень благодарен им за большую работу по переводу книги «Теория и практика кодов, контролирующих ошибки» на русский язык. Используя возможность, предоставленную мне издательством «Мир», я обращаюсь к советскому читателю. Он несомненно заметит, что книга адресована как инженерам, так и математикам, работающим в области приложений, и что в ней декодерам и алгоритмам декодирования уделяется гораздо больше внимания, чем в других книгах. Это связано отчасти с моими научными интересами и отчасти с широким распространением декодеров, исправляющих ошибки, за последнее десятилетие. Найти хороший алгоритм декодирования сейчас так же важно, как и найти хороший код. Читатель обнаружит также, что в книге недостаточно отражен крупный вклад советских исследователей в эту область. Частично это объясняется моей неосведомленностью, частично тем, что во многих советских работах принят более высокий уровень математической строгости, чем принятый в данной книге, и, наконец, тем, что советские исследователи не столь интенсивно работают в области алгоритмов декодирования, которая интересует меня больше всего. Я хотел бы поблагодарить переводчиков и редактора за исправление многочисленных ошибок, которые они нашли, и принимаю ответственность за оставшиеся ошибки. Р. Э. Блейхут
Монография известного американского специалиста, адресованная тем, кто непосредственно разрабатывает программы и аппаратуру помехоустойчивого кодирования. В ней впервые излагается разработанный автором единый подход к кодированию и декодированию, основанный на дискретном преобразовании Фурье. Для чтения книги достаточно знать математику в объеме втузовских программ (первые главы содержат необходимые сведения по алгебре). Она может служить и основой для курсов лекций, и пособием при первоначал.
Монография известного американского специалиста, адресованная тем, кто непосредственно разрабатывает программы и аппаратуру помехоустойчивого кодирования. В ней впервые излагается разработанный автором единый подход к кодированию и декодированию, основанный на дискретном преобразовании Фурье. Для чтения книги достаточно знать математику в объеме втузовских программ (первые главы содержат необходимые сведения по алгебре). Она может служить и основой для курсов лекций, и пособием при первоначальном ознакомлении с предметом.
Для математиков-прикладников, программистов и инженеров, а также для аспирантов и студентов вузов. Книга «Теория и практика кодов, контролирующих ошибки» автора Ричард Э. Блейхут оценена посетителями КнигоГид, и её читательский рейтинг составил 8.60 из 10. Для бесплатного просмотра предоставляются: аннотация, публикация, отзывы, а также файлы для скачивания.
Книга: Р. Блейхут «Теория и практика кодов, контролирующих ошибки»
Производитель: «ЁЁ Медиа»
Монография известного американского специалиста, адресованная тем, кто непосредственно разрабатывает программы и аппаратуру помехоустойчивого кодирования. В ней впервые излагается разработанный автором единый подход к кодированию и декодированию, основанные на дискретном преобразовании Фурье. Дли чтения книги достаточно знать математику и объеме втузовских программ (первые главы содержат необходимые сведения по алгебре). Она может служить и основой для курсов лекций, и пособием при первоначальном ознакомлении с предметом. Для математиков-прикладников, программистов и инженеров, а также для аспирантов и студентов вузов. Воспроизведено в оригинальной авторской орфографии издания 1986 года (издательство`Мир`). В
Издательство: «ЁЁ Медиа» (1986)
Другие книги автора:
См. также в других словарях:
Исправляющие ошибки Коды — Обнаружение ошибок в технике связи действие, направленное на контроль целостности данных при записи/воспроизведении информации или при её передаче по линиям связи. Исправление ошибок (коррекция ошибок) процедура восстановления информации после… … Википедия
Коды, исправляющие ошибки — Обнаружение ошибок в технике связи действие, направленное на контроль целостности данных при записи/воспроизведении информации или при её передаче по линиям связи. Исправление ошибок (коррекция ошибок) процедура восстановления информации после… … Википедия
Коды исправляющие ошибки — Обнаружение ошибок в технике связи действие, направленное на контроль целостности данных при записи/воспроизведении информации или при её передаче по линиям связи. Исправление ошибок (коррекция ошибок) процедура восстановления информации после… … Википедия
Обнаружение и исправление ошибок — Обнаружение ошибок в технике связи действие, направленное на контроль целостности данных при записи/воспроизведении информации или при её передаче по линиям связи. Исправление ошибок (коррекция ошибок) процедура восстановления… … Википедия
Код Рида — Коды Рида Соломона (англ. Reed–Solomon codes) недвоичные циклические коды, позволяющие исправлять ошибки в блоках данных. Элементами кодового вектора являются не биты, а группы битов (блоки). Очень распространены коды Рида Соломона,… … Википедия
Избыточное кодирование — Обнаружение ошибок в технике связи действие, направленное на контроль целостности данных при записи/воспроизведении информации или при её передаче по линиям связи. Исправление ошибок (коррекция ошибок) процедура восстановления информации после… … Википедия
Избыточность данных — Обнаружение ошибок в технике связи действие, направленное на контроль целостности данных при записи/воспроизведении информации или при её передаче по линиям связи. Исправление ошибок (коррекция ошибок) процедура восстановления информации после… … Википедия
Контрольный код — Обнаружение ошибок в технике связи действие, направленное на контроль целостности данных при записи/воспроизведении информации или при её передаче по линиям связи. Исправление ошибок (коррекция ошибок) процедура восстановления информации после… … Википедия
Коррекция ошибок — Обнаружение ошибок в технике связи действие, направленное на контроль целостности данных при записи/воспроизведении информации или при её передаче по линиям связи. Исправление ошибок (коррекция ошибок) процедура восстановления информации после… … Википедия
Помехоустойчивое кодирование — Обнаружение ошибок в технике связи действие, направленное на контроль целостности данных при записи/воспроизведении информации или при её передаче по линиям связи. Исправление ошибок (коррекция ошибок) процедура восстановления информации после… … Википедия
Код коррекции ошибок Рида-Соломона — Коды Рида Соломона недвоичные циклические коды, позволяющие исправлять ошибки в блоках данных. Элементами кодового вектора являются не биты, а группы битов (блоки). Очень распространены коды Рида Соломона, работающие с байтами (октетами). Код… … Википедия
Коды Боуза — Чоудхури — Хоквингхема (БЧХ-коды) — в теории кодирования это широкий класс циклических кодов, применяемых для защиты информации от ошибок (см. Обнаружение и исправление ошибок). Отличается возможностью построения кода с заранее определёнными корректирующими свойствами, а именно, минимальным кодовым расстоянием. Коды Рида — Соломона являются частным случаем БЧХ-кодов.
Содержание
Формальное описание
БЧХ-код является циклическим кодом, который можно задать порождающим полиномом. Для его нахождения в случае БЧХ-кода необходимо заранее определить длину кода n (она не может быть произвольной) и требуемое минимальное расстояние . Найти порождающий полином можно следующим образом.
Построение
Для нахождения порождающего полинома необходимо выполнить несколько этапов:
Примеры кодов
Примитивный 2-ичный (15,7,5) код
16-ричный (15,11,5) код (код Рида — Соломона)
g(x) = (x − α)(x − α 2 )(x − α 3 )(x − α 4 ) = x 4 + α 13 x 3 + α 6 x 2 + α 3 x + α 10
Каждому элементу поля GF(16) можно сопоставить 4 битам, поэтому одно кодовое слово эквивалентно 60=15*4 битам, таким образом набору из 44 бит ставится в соответствие набор из 60 бит. Можно сказать, что такой код работает с полубайтами информации.
Кодирование
Для кодирования кодами БЧХ применяются те же методы, что и для кодирования циклическими кодами.
Методы декодирования
Коды БЧХ являются циклическими кодами, поэтому к ним применимы все методы, используемые для декодирования циклических кодов. Однако существуют гораздо лучшие алгоритмы, разработанные именно для БЧХ-кодов.
Алгоритм Питерсона — Горенстейна — Цирлера (ПГЦ)
.
Составим полином локаторов ошибок:
Корнями этого полинома являются элементы, обратные локаторам ошибок. Помножим обе части этого полинома на . Полученное равенство будет справедливо для :
.
Учитывая (2) и то, что (то есть меняется в тех же пределах, что и ранее) получаем систему линейных уравнений:
Или в матричной форме
См. также
Литература
Полезное
Смотреть что такое «Код Боуза — Чоудхури — Хоквингема» в других словарях:
Код Боуза-Чоудхури-Хоквингема — Коды Боуза Чоудхури Хоквингхема (БЧХ коды) в теории кодирования это широкий класс циклических кодов, применяемых для защиты информации от ошибок (см. Обнаружение и исправление ошибок). Отличается возможностью построения кода с заранее… … Википедия
Код Рида — Соломона — Коды Рида Соломона недвоичные циклические коды, позволяющие исправлять ошибки в блоках данных. Элементами кодового вектора являются не биты, а группы битов (блоки). Очень распространены коды Рида Соломона, работающие с байтами (октетами). Код… … Википедия
Код коррекции ошибок Рида-Соломона — Коды Рида Соломона недвоичные циклические коды, позволяющие исправлять ошибки в блоках данных. Элементами кодового вектора являются не биты, а группы битов (блоки). Очень распространены коды Рида Соломона, работающие с байтами (октетами). Код… … Википедия
Код Рида-Соломона — Коды Рида Соломона недвоичные циклические коды, позволяющие исправлять ошибки в блоках данных. Элементами кодового вектора являются не биты, а группы битов (блоки). Очень распространены коды Рида Соломона, работающие с байтами (октетами). Код… … Википедия
Код Рида — Коды Рида Соломона (англ. Reed–Solomon codes) недвоичные циклические коды, позволяющие исправлять ошибки в блоках данных. Элементами кодового вектора являются не биты, а группы битов (блоки). Очень распространены коды Рида Соломона,… … Википедия
КОД С ИСПРАВЛЕНИЕМ ОШИБОК — код, корректирующий ошибки, множество сообщений, предназначенных для передачи по каналу связи с шумами, обладающее тем свойством, что окрестность ошибок каждого сообщения (т. е. совокупность искаженных вариантов этого сообщения) не пересекается с … Математическая энциклопедия
Контрольный код — Обнаружение ошибок в технике связи действие, направленное на контроль целостности данных при записи/воспроизведении информации или при её передаче по линиям связи. Исправление ошибок (коррекция ошибок) процедура восстановления информации после… … Википедия
РС код — Коды Рида Соломона недвоичные циклические коды, позволяющие исправлять ошибки в блоках данных. Элементами кодового вектора являются не биты, а группы битов (блоки). Очень распространены коды Рида Соломона, работающие с байтами (октетами). Код… … Википедия
Турбо-код — Турбо код параллельный каскадный блоковый систематический код, способный исправлять ошибки, возникающие при передаче цифровой информации по каналу связи с шумами. Синонимом турбо кода является известный в теории кодирования термин … … Википедия
Линейный код — В области математики и теории информации линейный код это важный тип блокового кода, использующийся в схемах определения и коррекции ошибок. Линейные коды, по сравнению с другими кодами, позволяют реализовывать более эффективные алгоритмы… … Википедия
. Найти порождающий полином можно следующим образом.
.
. Полученное равенство будет справедливо для 
:
.
(то есть 
меняется в тех же пределах, что и ранее) получаем систему линейных уравнений:
