4.2. Китайская теорема об остатках
Рассмотрим более детально формулу (4.1), задающую ДПФ над полем . Например, для того, чтобы вычислить ДПФ над полем вектора длины, требуется умножений в поле. Как известно, умножение является одной из наиболее затратных по времени операций, т.е. алгоритм ДПФ имеет сложность порядка O(. Известные алгоритмы многомерного преобразования Фурье, а так же БПФ (быстрое преобразование Фурье) позволяют снизить эту цифру до N*logN умножений. Данные алгоритмы основаны на следующей китайской теореме об остатках.
Теорема 4.2.1. (Китайская теорема об остатках, единственность)
Для заданного множества целых положительных попарно взаимно-простых чисели множества неотрицательных целых чисел
при, система сравнений
имеет не более одного решенияc в интервале
Теорема 4.2.2. (Китайская теорема об остатках, существование)
Пусть –произведение целых положительных попарно взаимно-простых положительных чисел, пусть и пусть удовлетворяют равенству , тогда единственным решением системы сравнений
будет
Эта теорема позволяет каждое число n,0≤n<M однозначно задать системой остатков по модулям , i=1,k.
- Введение
- В дипломной работе рассмотрен спектральный метод кодирования кодов Рида-Соломона над полем gf(). В основе спектрального описания рс-кодов лежит дискретное преобразование Фурье (дпф над конечным полем.
- Раздел 1. Основы теории помехоустойчивого кодирования
- 1.1 Основные определения
- 1.2 Классификация кодов
- 1.3 Принципы обнаружения и исправления ошибок
- 1.4. Корректирующая способность кода
- Раздел 2. Арифметика и структура конечных полей галуа. Многочлены над полями галуа
- 2.1. Введение в теорию конечных полей
- 2.2 Векторное пространство над конечными полями. Линейная зависимость и независимость
- 2.3 Арифметика полиномов, заданных над конечным полем
- 2.4. Расширенные конечные поля
- 2.5 Мультипликативный порядок элементов поля. Примитивные элементы. Другой подход к построению расширения поля Галуа
- 2.6. Некоторые свойства расширенных конечных полей
- Раздел 3. Линейные блоковые коды
- 3.1. Линейные коды
- 3.2. Определение циклического кода. Порождающий полином
- 3.3. Систематический циклический код
- 3.4. Коды Рида-Соломона
- Раздел 4. Спектральное описание циклических кодов
- 4.1. Дискретное преобразование Фурье
- 4.2. Китайская теорема об остатках
- 4.3. Трехмерное преобразование Фурье в поле
- 4.4 Быстрое преобразование Фурье бпф длины 3
- 4.5. Быстрое преобразование Фурье длины 5
- 4.6 Быстрое преобразование Фурье длины 17
- 4.8. Несистематические бпф-укорочения
- Заключение
- Список использованной литературы
- Приложения Приложение 1. Анализ временных характеристик кодера кодов Рида-Соломона
- Приложение 2 Листинг программы