Оглавление Предисговие к русскому изданию 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
Формат: DjVu
Страниц: 593
Размер: 10.2 MB
Язык: Русский
Монография посвящена теории кодирования информации. Все понятия излагаются подробно и подкреплены серьезным математическим аппаратом, хотя в аннотации книги и сказано «от читателя не требуется специальных знаний», но данное требование явно занижено. Книга является одним из авторитетных фундаментальных изданий в области кодирования и знакома многим математикам и инженерам в области радиотехники, систем связи, вычислительной техники, АСУ.
Скачать У.Питерсон, Э.Уэлдон — Коды, исправляющие ошибки [1976, DjVu]
Оглавление Предисговие к русскому изданию 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 г., в значительной степени восполняет указанный недостаток. Однако, как отмечается в предисловии ко второму изданию, здесь не нашли отражения работы советских ученых, Между тем к моменту его выхода в свет в нашей стране были получены весьма интересные результаты, опубликовано несколько монографий по теории кодирования, проведены два Международных симпозиума по теории информации, на которых зарубежные ученые имели возможность познакомиться с результатами, полученными советскими учеными.
Ресурс не предоставляет электронные версии произведений, а занимается лишь коллекционированием и каталогизацией ссылок, присылаемых и публикуемых на форуме нашими читателями. Если вы являетесь правообладателем какого-либо представленного материала и не желаете чтобы ссылка на него находилась в нашем каталоге, свяжитесь с нами и мы незамедлительно удалим её. Файлы для обмена на трекере предоставлены пользователями сайта, и администрация не несёт ответственности за их содержание. Просьба не заливать файлы, защищенные авторскими правами, а также файлы нелегального содержания!