Питерсон уэлдон коды исправляющие ошибки скачать

Оглавление Предисговие к русскому изданию 1редисаовие авторов 5 7 9 9 11 !3 15 19 25 !. Возможности исправления ошибок с помощью линейных кодов, . „91 4.1. Границы минимального расстояния для блоковых кодов . . . . . . 91 4.2. Границы вероятности ошибки для блоковых кодов, используемых при передаче по двоичному симметричному каналу, . .

. . . . . 103 4.3. Обсуждение границ для блоковых кодов……….. „1Гй 4,4. Границы минимального расстонния для сверточных кодов,…. !!6 1. Проблема кодирования 1.1. Канал связи 1.2. Несколько общих замечаний о кодах, обнаруживающих и исправляющих ошибки . 1.3. Типы кодов… 1 4. Блоковые коды 1.5. Дреновядные коды 1.6. Проблема кодирования Ь Введение в алгебру,… 2.1.

Группы…, . 2.2. Кольца 2.3, Поля 2,4, Подгруппы и факторгруппы…. 2.5. Векторные пространства и линейные алгебры 2.6. Матрицы !. Линейные коды . 3.1. Метрика Хэмминга н метрика Ли.. 3.2. Описание линейных блоковых кодов при помощи матриц . З.З. Описание древовидных линейных кодов при помощи матриц . 3.4. Стандартное расположение 3.5.

Поэтапное декодирование для блоковых кодов ., 3.6. Модулярное представление линейных блоковых кодов . 3.7. Эквивалентность линейных блоковых кодов .. 3.8. Распределения весов и тождества Мак-Уильямс . 3.9. Максимально разнесенные коды .

29 29 32 34 35 39 42 52 52 54 59 65 70 73 76 78 84 Грзницы вероятности ошибки для сверточных кодов, используемых при передаче по двоичному симметричному каналу……. 120 Границы для кодов, исправляющих и обнаруживающих пакеты ошибок………….,…….,… 125 4.5 4.6 5. Важные линейные блоковые коды г.

! 5.2 5.3 5.4 Коды Рида — Маллера 5.5 5.6 5.7 5.8. Теоретико-трефовые коды 5.9. Низкоплотностпые коды . 5.10. Каскадные коды .. 6. Кольца миогочленов и поля Галуа . 7. Линейные переключательные схемы……….,,…. 195 Определения…. !95 Умножение и деление многочлеиов . . . . . . . , . .

. . . . !96 Вычисления в алгебрах многочленов н полях Галуа . . . . . . . 203 Линейные рекурреитные соотношения и генераторы с регистром сдвига 206 Е-преобразования, передаточные функции н синтез . . . . . . , 213 Анализ обшей линейной переключательной схемы с конечным числом состояний ….. . . . . . . .

. . , , . . . . . . . . 221 Е Цинлические коды . 232 Циклнческне коды н идеалы . 232 Матричное описание циклических кодов .. . . . . . . . . . . 238 Описание циклических кодов при помощи ассоциированных мпогочленое 243 Колы Хзмминга…..,……….,….. 246 Коды, задаваемые последовательностями максимальной длины… 249 Некоторые двоичные циклические коды .. . .

, . . . . . . . . 251 Методы кодирования 251 Обнаружение ошибок с помощью циклических кодов .. . . . . . 256 Некоторые простые методы исправления ошибок длн коротких циклических кодов . . . , , . . . , . . . . . , . . . . . . . 258 6.! 6.4. 6.5 6.7 6.8 7.1 7.2 7.3 7.4 7.5 7.6 8.!. 8.2 8.3. 8.4. 8.5. 8.6. 8.7. 8.8 8.9 Коды Хзммияга (23, ! 2! -код Голе я Оптимальные коды лля двоичного симметричного канала Двоичные коды с большим минимальным расстонвнем ., Колы, получаемые с помощью матриц Адамара Произведении кодов…

Идеалы, классы вычс»гов и кольцо классов вычетов, Идеалы и классы вычетов целых чисел… Идеалы многочленов и классы вычетов .. Илгебра классов вычетов многочленов Поля Галуа…. Мультипликативная группа поля Галуа, . Структура конечных полей.

Резюме . Векторные подпространства и линейные преобразования полей . 134 . 134 . 138 . !39 . 14! . 144 . 149 . 150 156 . 159 . !60 166 . 166 . 168 . 170 . 172 . !77 . 183 185 конечных . . !88 . 351 . 36! декодирования . 367 . 375 . 391 ошибок, построен- . 398 . 399 . 405 . 406 . 410 . 412 исправляют . 418 исправляют , 423 8.10. Укороченные циклические коды .

8.!1. Симметрия кодов…. 8.12. Произведение циклических кодов 8.13. Квадратично-вычетные коды 8.14. Квазициклические коды…, 8,15. Коды, основанные на кнтзйской теореме об остатках . !. Коды Боузз — Чоудхури — Хоквиигема 9.1. Граница БЧХ . 9.2. Определение кодов… 9.3. Истинный минимальный вес БЧХ-кодов .. 9.4. Процедура исправления ошибок .. 9.5. Усовершенствования пронедуры исправления ошибок .

9.6. Упрощения в двоичном случае . 9.7. Исправление стираний и ошибок 98. Негзциклическне коды… 1О. Коды с мажоритарным декодировнннем .. 10Л. Мажоритарное декодирование … 10.2. Евклидово-геометрические коды !0.3 Проективно-геометрические коды !0.4. Модификации основного алгоритма мажоритарного !ОЛ. Обобщенные коды Рида — Маллера . !0.6. Полиномиальные коды 11. Циклические коды, исправляющие пакеты ошибок, .

11.1. Аналитические методы построения кодов ., 11.2. Некоторые хорогпие коды, исправлиющие пакегы иые с помощью ЭВМ, 11.3. Декодирование . 11.4. Исправление многократных пакетов 11.5. Исправление пакетов и случайных ошибок… 12. Синхронизация блоковых кодов … 12.1. Коды, которые только восстанавливают синхрониэкцию 12.2, Коды, которые восстананливают синхронизацшо или аддитивные ошибки 12.3.

Коды, которые восстанавливают синхронизацию и аддитивные ошибки . !3. Сверточные коды, исправляющие случайные ошибки . 13.1. Кодирование и вычисление синдрома . 13.2. Исправление и размпомгение ошибок 13.3. Коды, исправляющие одиночные и двойные ошибки !3.4. Самоортогональные коды 13.5. Ортогопализируемые коды 13.8. Коды, построенные с помощью ЭВМ .. !37. Алгоритм декодирования Витерби .. 13.8. Последовательное декодирование …

. 270 . 273 . 280 . 284 . 287 . 292 . ЗО! . ЗО! . ЗРО . 315 . 321 . 331 . 337 . 429 . 429 436 . 439 . 441 . 446 . 449 . 458 14. Сверточиые коды, исправляющие пакеты ошибок .. !4.1. Некоторые оцределепия 14.2. Коды Берлекзмпа — Препарата — Месса 14.3. Колы Ивадаре . 14.4. Низкоскоростные коды 14.5.

Коды, исправляющие пакеты ошибок и случайные ошибки . 465 . 465 . 466 . 473 . 480 . 481 15. Арифметические коды . 489 15.1. Определение пончтий сошибка» и «расстояние» . . . . . . . . . 489 15.2. Свойства арифметического веса в двоичном случае……..

491 15.3. Арифметические коды . 493 15зй Совершенные арифметические коды, исправляющие одиночные ошибки 496 15.5. Арифметняеские коды с большим минимальным расстоянием… 498 15.6. Самодополияюшиеся АФ + В-коды,,…,……. 501 15.7. Реализация АУ- и А)7+ В-кодов……. 502 15.8. Раздельные сумматор и проверяющее устройство…….. 504 Приложение А. Неравенства, включающие биномиальные коэффициенты .. 509 Приложение Б. Краткая таблица зяачений энтропии (по основанию 10) н ее первой произиодной , . .

. . . . . . . . . . 512 Приложение Б. Таблицы неприводимых многочленов над полем бг»(2) . , 513 Приложение Г. Перечень двоичных циклических кодов нечетной длины . . 533 Литература . 575 Предисловие к русскому изданию На современном этапе развития средств обработки информа. ции все ббльшую важность приобретают сложные территориально рассредоточенные информационные системы, базирующиеся на тесном взаимодействии вычислительной техники и средств передачи информации. Работоспособность таких систем зависит от достоверности ввода, хранения и обработки информации, а также от помехоустойчивости передачи ее по каналам протяженностью сотни тысяч километров.

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

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

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

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

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

Коды, исправляющие ошибки

	Питерсон У., Уэлдон Э. Коды, исправляющие ошибки. Изд. «Мир», 1976. Монография посвящена теории кодирования информации. Все необходимые для построения теории кодирования алгебраические понятия излагаются подробно. Рассматриваются прикладные аспекты теории.

Оглавление

ПРЕДИСЛОВИЕ РЕДАКТОРА ПЕРЕВОДА
ГЛАВА 1. ПРОБЛЕМА КОДИРОВАНИЯ
1.2. Несколько замечаний о двоичных кодах, обнаруживающих и исправляющих ошибки
1.3. Блоковые коды
1.4. Расстояние Хэмминга
1.6. Проблема кодирования
Замечания
ГЛАВА 2. АЛГЕБРАИЧЕСКОЕ ВВЕДЕНИЕ
2.2. Кольца
2.3. Поля
2.4. Подгруппы и факторгруппы
2.5. Векторные пространства и линейные алгебры
2.6. Матрицы
Замечания
ГЛАВА 3. ЛИНЕЙНЫЕ КОДЫ
3.1. Определение линейного кода
3.2. Описание линейных кодов при помощи матриц
3.3. Стандартная расстановка
3.4. Поэтапное декодирование
3.5. Модулярное представление линейных кодов
3.6. Эквивалентность линейных кодов
Замечания
ГЛАВА 4. ВОЗМОЖНОСТИ ИСПРАВЛЕНИЯ ОШИБОК С ПОМОЩЬЮ ЛИНЕЙНЫХ КОДОВ
4.1. Граница Плоткина
4.2. Граница Варшамова-Гилберта
4.3. Граница, основанная на принципа плотной упаковки сфер
4.4. Граница, основанная на случайном выборе кода
4.5. Обсуждение границ
4.6. Границы для кодов, исправляющих или обнаруживающих пачки ошибок
Замечания
ГЛАВА 5. ВАЖНЕЙШИЕ ЛИНЕЙНЫЕ КОДЫ
5.1. Коды Хэмминга
5.2. Веса кодовых слов в коде Хэмминга
5.3. (23,12)-код Голея
5.4. Оптимальные коды для двоичного симметричного канала
5.5. Коды Рида — Маллера
5.6. Коды Макдональда
5.7. Коды, получаемые с помощью матриц Адамара
5.8. Итеративные коды
Замечания
ГЛАВА 6. КОЛЬЦА МНОГОЧЛЕНОВ И ПОЛЯ ГАЛУА
6.1. Идеалы, классы вычетов и кольцо классов вычетов
6.2. Идеалы и классы вычетов целых чисел
6.3. Идеалы многочленов и классы вычетов
6.4. Алгебра классов вычетов многочленов
6.5. Поля Галуа
6.6. Мультипликативная группа поля Галуа
Замечания
ГЛАВА 7. ЛИНЕЙНЫЕ ПЕРЕКЛЮЧАТЕЛЬНЫЕ СХЕМЫ
7.2. Умножение и деление многочленов
7.3. Вычисления в алгебрах многочленов и полях Галуа
7.4. Линейные рекуррентные соотношения и генераторы с регистром сдвига
7.5. Анализ линейных переключательных схем
7.6. Анализ общей линейной переключательной схемы с конечным числом состояний
Замечания
ГЛАВА 8. ЦИКЛИЧЕСКИЕ КОДЫ
8.1. Циклические коды и идеалы
8.2. Матричное описание циклических кодов
8.3. Последовательности максимальной длины
8.4. Кодирование с помощью регистра сдвига, содержащего k разрядов
8.5. Кодирование с помощью регистра сдвига, содержащего n – k разрядов
8.6. Обнаружение ошибок с помощью циклических кодов
8.7. Двоичные коды Хэмминга
8.8. Обобщенные коды Хэмминга
8.9. Укороченные циклические коды
Замечания
ГЛАВА 9. КОДЫ БОУЗА – ЧОУДХУРИ
9.2. Двоичные коды
9.3. Коды Рида — Соломона
9.4. Метод исправления ошибок
9.5. Другой способ исправления ошибок для двоичных кодов
9.6. Обнаружение ошибок с помощью кодов Боуза — Чоудхури
9.7. Использование кодов Боуза — Чоудхури при передаче по стирающему каналу
Замечания
ГЛАВА 10. ЦИКЛИЧЕСКИЕ КОДЫ, ИСПРАВЛЯЮЩИЕ ПАЧКИ ОШИБОК
10.1. Коды Файра
10.2. Возможности кодов Файра исправлять ошибки
10.3. Другие коды, исправляющие пачки ошибок
10.4. Двоичные коды, исправляющие пачки только с четным или только с нечетным числом ошибок
10.6. Практическая реализация кодов, исправляющих пачки ошибок
10.6. Другой метод исправления ошибок
10.7. Другой подход к задаче исправления пачек ошибок
Замечания
ГЛАВА 11. ДРУГИЕ СПОСОБЫ ДЕКОДИРОВАНИЯ
11.1. Общее декодирующее устройство для циклических кодов
11.2. Использование симметричности кода при поэтапном декодировании
11.3. Алгоритмы декодирования Рида
Замечания
ГЛАВА 12. РЕКУРРЕНТНЫЕ КОДЫ
12.1. Определение рекуррентного кода
12.2. Коды Хегельбергера, исправляющие пачки ошибок
12.3. Обнаружение пачек ошибок с помощью рекуррентных кодов
12.4. Рекуррентный код, исправляющий лачки ошибок и построенный на основе циклического кода
12.5. Последовательное декодирование
ГЛАВА 13. КОДЫ ДЛЯ ПРОВЕРКИ АРИФМЕТИЧЕСКИХ ОПЕРАЦИЙ
13.2. AN-коды
13.3. Самодополняющиеся (AN+B)-коды
13.4. Реальное осуществление AN- и (AN+B)-кодов
13.6. Раздельные сумматор и проверяющее устройство
ПРИЛОЖЕНИЕ А. НЕРАВЕНСТВА, ВКЛЮЧАЮЩИЕ БИНОМИАЛЬНЫЕ КОЭФФИЦИЕНТЫ
ПРИЛОЖЕНИЕ Б. КРАТКАЯ ТАБЛИЦА ЗНАЧЕНИЙ ЭНТРОПИИ (ПО ОСНОВАНИЮ 10) И ЕЕ ПЕРВОЙ ПРОИЗВОДНОЙ
ПРИЛОЖЕНИЕ В. ТАБЛИЦЫ НЕПРИВОДИМЫХ МНОГОЧЛЕНОВ НАД ПОЛЕМ GF(2)

Питерсон, Уильям Уэсли — Коды, исправляющие ошибки [Текст] : Пер. с англ.