Алгоритмы теории чисел

Решение

Исправление ошибок в циклическом коде

Решение

Находим произведение x ^n-k× G(x) = х⁵ × G(x) = х⁵ × (х¹⁰ Å х⁶ Å х⁴ Å Å х³ Å1) = х¹⁵ Å х¹¹ Å х⁹ Å х⁸ Å х⁵

Получаем частное G(x) × x ^n-k х¹⁵ Å х¹¹ Å х⁹ Å х⁸ Å х⁵

^{---------------------} = ^{-------------------------------------------------}

Р(х) х⁵ Å х⁴ Å х² Å 1

Остаток будет: R (x) = х⁴ Å х² Å 1.

Т.о. кодовая комбинация будет: х¹⁵ Å х¹¹ Å х⁹ Å х⁸ Å х⁵ Å х⁴ Å х² Å 1 =

= 010001011001 10101

------------------ -------

k ρ

Производится по остаткам от деления принятой комбинации на образующий многочлен Р(х): если принятая комбинация делится на Р(х) без остатка, то код принят без ошибок. При наличии остатка определяют его вес w.

Если w £ s (число исправляемых ошибок), то F(x) Å остаток = правильная кодовая комбинация.

Если w > s, то циклически сдвигаем полученную кодовую комбинацию влево на один разряд. Полученную комбинацию делим на образующий многочлен Р(х). Определяем вес остатка w.

Если w £ s, то сдвинутая комбинация Å остаток. Сдвигаем вправо циклически на один разряд и получаем правильную кодовую комбинацию.

Если w > s, то циклически сдвигаем сдвинутую кодовую комбинацию влево на один разряд. Полученную комбинацию делим на образующий многочлен Р(х). Определяем вес остатка w.

И так до тех пор пока не подучим w £ s.

Пример: F(x) = 1000110. P(x) = х³ Å х Å 1.

Исправить ошибку при ее наличии. s = 1.

1.

w =2. w > s.

Сдвигаем F(x) влево на один разряд: 0001101

2.

w =2. w > s.

Сдвигаем F(x) влево на один разряд: 0011010

3.

w =3. w > s.

Сдвигаем F(x) влево на один разряд: 0011010

4.

w =2. w > s.

Сдвигаем F(x) влево на один разряд: 0011010

5.

w =1. w = s.

Суммируем по модулю два: 1101000 Å 1 = 1101001.

Циклически сдвигаем вправо на 4 разряда и получаем исправленную комбинацию: 1001110.

4.5 Выполнение работы

Каждый студент получает номер задания для написания программы, реализующей конкретную задачу. Инструментарий не ограничивается.

Программа должна предусматривать ввод информационных символов, ввод образующей матрицы или многочлена, выдачу результатов.

4.6 Содержание отчета

1. Наименование и цель работы

2. Краткие теоретические сведения

3. Описание программы

4. Схема алгоритма

5. Текст программы

6. Контрольный пример

7. Выводы

4.7 Контрольные вопросы

1. Что такое коды ОНК?

2. В чем различие методик Шеннона-Фано и Хаффмена?

3. Основные шаги построения помехоустойчивых кодов.

4. Этапы нахождения ошибок в линейном систематическом коде, коде Хэмминга, циклическом коде.

5 ЛАБОРАТОРНАЯ РАБОТА № 5

5.1 Цель работы

Закрепить знания в использовании основных алгоритмов теории чисел.

5.2 Темы лабораторной работы №5

1. Нахождение НОД по алгоритму Евклида.

2. Нахождение функции Эйлера.

3. Нахождение обратной величины в модулярной арифметике.

4. Решение сравнения.

5. Решение системы сравнений.

6. Быстрое возведение в степень.

7. Возведение в степень и умножение по модулю

5.3 Основные определения

Модулярная арифметика часто называется “арифметикой часов”. Если прибавить 14 часов к 3 часам после полудня, то получится 5 часов утра следующего дня:

3 + 14 º 5 (mod 12)

или

(3 + 14) mod 12 = 5.

Это арифметика по модулю 12.

Обычная запись в модулярной арифметике

a º b (mod n)

читается так: “ a сравнимо с b по модулю n ”.

Это соотношение справедливо для целых значений a, b и n ¹ 0, если и только если

а = b + k • n

для некоторого целого k.

Отсюда, в частности, следует

n | (a ─ b).

Это читается как “ n делит (a ─ b)”.

Если a º b (mod n), то b называют вычетом числа a по модулю n.

Операцию нахождения вычета числа а по модулю n

a (mod n)

называют приведением числа а по модулю n или приведением по модулю.

В нашем примере

(3 + 14) mod 12 = 17 mod 12 = 5

или

17 º 5 (mod 12),

число 5 является вычетом числа 17 по модулю 12.

Набор целых чисел от 0 до (n – 1) называют полным набором вычетов по модулю n.

Это означает, что для любого целого а (а > 0) его вычет r по модулю n есть некоторое целое число в интервале от 0 до (n – 1), определяемое из соотношения

r = a – k • n,

где k – целое число.

Например, для n = 12 полный набор вычетов:

{0, 1, 2, …, 11}.

Обычно используют вычеты

r Î {0, 1, 2, …, n – 1},

но иногда полезны вычеты в диапазоне целых:

r Î {– ½ (n – 1), …, ½ (n – 1)}.

Важно, что

– 12 (mod 7) º – 5 (mod 7) º 2 (mod 7) º 9 (mod 7) и т.д.

Модулярная арифметика аналогична во многом обычной арифметике: она коммутативна, ассоциативна и дистрибутивна. Точнее говоря, целые числа по модулю n с использованием операций сложения и умножения образуют коммутативное кольцо при соблюдении законов ассоциативности, коммутативности и дистрибутивности.

Фактически можно сначала приводить по модулю n, а затем выполнять операции, либо сначала выполнять операции, а затем приводить по модулю n, поскольку приведение по модулю n является гомоморфным отображением из кольца целых в кольцо целых по модулю n:

(a + b) mod n = [ a (mod n) + b (mod n) ] mod n,

(a - b) mod n = [ a (mod n) - b (mod n) ] mod n,

(a • b) mod n = [ a (mod n) • b (mod n) ] mod n,

[a • (b + c) ] mod n = {[a • b (mod n) ] + [a • c (mod n) ]} mod n.

Криптография использует множество вычислений по модулю n, потому что задачи типа вычисления дискретных логарифмов и квадратных корней очень трудны.

Кроме того, с вычислениями по модулю удобнее работать, потому что они ограничивают диапазон всех промежуточных величин и результата.

Для модуля n длиной k бит промежуточные результаты любого сложения, вычитания или умножения будут не длиннее 2kбит. Поэтому возведение в степень в модулярной арифметике можно выполнить без генерации очень больших промежуточных результатов.

5.4 Теоретические сведения

Дата добавления: 2015-08-31