Реферат
з курсу "Теорія інформації та кодування"
Тема:
"СПЕЦІАЛЬНІ Коди"

1. Коди Фібоначчі

1.1 ЗОЛОТІ ПРОПОРЦІЇ
У математиці існує велика кількість ірраціональних (несумірних) чисел, тобто позначають довжину відрізка несумірної з одиницею масштабу. Ряд із них широко використовується як в математиці, так і в інших областях.
Наприклад: Число p = 2 p R / D = 3,14159 ..., яке представляє відношення довжини кола до її діаметра. Число e = 2,71828 ..., при цьому . Логарифми з основою e зручні для математичних розрахунків. Число Ö 2 = 1,44 ..., яке представляє відношення діагоналі до сторони квадрата і ряд інших чисел.
Особливу ірраціональне число a = (1 + Ö 5) / 2 = 1,61803, яке називається золота пропорція або золотий перетин і є результатом виконання завдання поділу відрізка в крайньому і середньому відношенні (рис. 1)
A C B
про o o
Рис. 1 Розподіл відрізка
Якщо заданий відрізок AB то необхідно знайти таку точку C, щоб виконувалася умова AB / CB = CB / AC.
Позначимо: x = CB / AC; (CB + AC) / CB = 1 +1 / x = x.
При цьому x ^2-x-1 = 0. Коріння цього рівняння рівні: x _1,2 = (1 ± Ö 5) / 2.
Позитивний корінь називається золотою пропорцією , А точка C - золотим перетином. Золота пропорція володіє рядом унікальних властивостей.

Пропорція 1,61 ... використовувалася в архітектурі, художніх творах, музиці з античних часів. З цим числом пов'язаний ореол містики, таємничості, божества і т.д.
В останнє десятиліття ця пропорція знайшла своє застосування в ЕОМ, АЦП-ЦАП, вимірах і т. д.
1.2 Числа Фібоначчі
З золотим перетином тісно пов'язані числа Фібоначчі відкриті італійським математиком Леонардо з Пізи (Фібоначчі) в XIII столітті, які обчислені за формулою:
(1)
Ці числа представляють ряд: 1, 1, 2, 3, 5, 8, 13, 21 ...

Ставлення сусідніх чисел Фібоначчі 1 / 1, 2 / 1, 3 / 2, 5 / 3, 8 / 5, 13 / 8, 21/13 ... в межі прагне до золотої пропорції

. (2)
Числа Фібоначчі володіють ще поряд корисних властивостей. Наприклад, залишки від ділення чисел Фібоначчі на 2 утворюють послідовність: 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, ... і т. д.
Узагальнені числа Фібоначчі або p-числа Фібоначчі обчислюються за рекуррентной формулою:
(3)
Де p = 0, 1, 2, 3, .... При р = 0 число j ₀ (n) збігається з двійковими розрядами 2 ⁿ (табл. 1) .

Таблиця 1

n	0	1	2	3	4	5
j 0 (n)	1	2	4	8	16	32

При р = 1 число j ₀ (n) збігається зі звичайним поруч Фібоначчі:
1, 1, 2, 3, 5, 8, ...
При р = число j ₀ (n) = 1 для будь-якого n ³ 0 одно:
1, 1, 1, 1, 1, 1, 1, 1, ...
1.3 Коди Фібоначчі
Будь-яке натуральне число N можна представити за допомогою p-чисел Фібоначчі
(4)
де: a _i Î {0, 1} - двійкова цифра i-го розряду; j _p (i) - вага i-го розряду;
Будь-яке натуральне число N можна представити також наступним способом:

(5)
Таке уявлення чисел N називається p-кодом Фібоначчі. Кожному p Î {0, 1, 2, ..., ¥} відповідає свій код, тобто їх кількість нескінченно.
При p = 0 p-код Фібоначчі співпадає з двійковим кодом.
Для 1-коду Фібоначчі кодові комбінації мають вигляд:
Таблиця 2

Як видно з таблиці 5 розрядним 1-кодом Фібоначчі можна закодувати 13 натуральних чисел від 0 до 12, при цьому кожному числу відповідає безліч комбінацій.

Коди Фібоначчі утворюють відповідну систему числення з набором арифметичних операцій.
Додавання: Віднімання:
0 +0 = 0; 0 - 0 = 0;
0 +1 = 1; 1 -1 = 0;
1 +0 = 1, 1 -0 = 1;
1 +1 = 111; 10-1 = 1;
1 +1 = 1001; 110 -1 = 11;
1000-1 = 111.
При складанні 2-х одиниць може бути:
1. J ₁ (n) + j ₁ (n) = j ₁ (n) + j ₁ (n-1) + j ₁ (n-2) т. е. дорівнює 1 і перенесення 1 у два молодших розряду.
2. J ₁ (n) + j ₁ (n) = j ₁ (n +1) + j ₁ (n-2) т. е. дорівнює 0 і перенос 1 у два розряди - попередній і наступний.
Коди Фібоначчі мають ряд корисних властивостей (наприклад, надмірність і т. д.), що дозволяють будувати швидкодіючі і перешкодостійкі АЦП ("фібоначчевие" АЦП), які реалізують спеціальні алгоритми перетворення. Коди Фібоначчі використовуються для діагностики ЕОМ, в цифрових фільтрах для поліпшення спектрального складу сигналу за рахунок перекодування та інших областях.

2. Двійкове ВІДБИТТЯ КОД. КОД ГРЕЯ
Код Грея відрізняється від двійкового коду тим, що при переході до наступної кодової комбінації змінюється тільки один елемент кодової комбінації (табл. 3).
Якщо при передачі повідомлень за допомогою коду Грея одночасно змінюється кілька розрядів коду, то це свідчить про помилку, в цьому полягає виявляє здатність коду Грея.
Код Грея, не виважений і непридатний для обчислювальних операцій без попереднього перекладу в двійковий код.

Якщо позначити: a i   - Двійковий код; b i - Код Грея, то правило переходу із двійкового коду до коду Грея має вигляд: b i = a i a i +1 де - Підсумовування по mod 2 a i +1 - a i - із зсувом на один розряд вправо. Приклад: 1) a i = 1 1 1 0 1 1 1 1 0 1 b i = 1 0 0 1 1 2) a i = 1 1 1 1 1 1 1 1 b i = 1 0 0 0

Таблиця 3

Число	Дв. Код	Код Грея
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15	0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111	0000 0001 0011 0010
		0110 0111 0101 0100
		1100 1101 1111 1110
		1010 1011 1001 1000

Схема кодера Грея наведена на рис. 2. Як видно з кодер Грея реалізується за допомогою регістра RG, ​​сдвигового регістру SRG і суматора за модулем 2 SM2.
Правила переходу з коду Грея в двійковий код. Існує кілька способів переходу.
1. Використовується наступний алгоритм:
a _n-1 = b _n-1;
a _i = a _{i +1}   b _i.
де a _n-1 - Значення старшого розряду двійкового числа.

a i b i nnnn n Рис.2. Схема кодера Грея

RG

SRG

SM2

Приклад 1. Дана запис числа кодом Грея b _i = 10101 ® b ₄ b ₃ b ₂ b ₁ b ₀ отримати двійковий запис. Використовуючи наведені вище формули, одержимо
a ₄ = b ₄ = 1;
a ₃ = a ₄ b ₃ = 1 0 = 1;
a ₂ = a ₃ b ₂ = 1 1 = 0;
a ₁ = a ₂ b ₁ = 0 0 = 0;
a ₀ = a ₁ b ₀ = 0 1 = 1;
a _i = a ₄ a ₃ a ₂ a ₁ a ₀ = 11001

2. Перехід здійснюється за алгоритмом a _i = - Тобто як сума по модулю 2 всіх попередніх значень
Приклад 2. Дана запис числа кодом Грея b _i = 11001. При цьому двійковий запис дорівнює a _i = 10101;
Правила переходу з двійкового коду та коду Грея до десяткового запису
Для двійкового коду:
Для коду Грея:
для непарних " 1 " знак "+", для парних " 1 " знак "-".
Приклад 3. Дана запис числа двійковим кодом a _i = .
При цьому десяткова запис дорівнює
a ₁₀ = 1 × 2 ⁵ + 1 × 2 ⁴ + 1 × 2 ² +1 × 2 ¹ = 32 +16 +4 +2 = 54.
Приклад 4. Дана запис числа двійковим кодом a _i = 110110. Отримати код Грея і перетворити його в десяткову запис.
Отримаємо код Грея

a _i = 1 0 1 1 0
1 1 0 1 1 0
b _i = 1 0 1 1 0 1.
Отримаємо десяткову запис
b ₁₀ = 1 × ⁽² Червень -1) - 1 × (2 ⁴ -1) + 1 × (2 ³ -1) - 1 × (2 ¹ -1) = 63-15 +7-1 = 54.
Гідність коду Грея: Простота перекладу в двійковий код і назад, а також до десяткового запису.
Застосування коду Грея: Код Грея, найчастіше, використовується для надійного переходу від аналогового подання інформації до цифрової і назад, тобто в аналого-цифрових перетворювачах (АЦП).

Список Літератури
1. Вернер М. Основи кодування. - М.: Техносфера, 2004.
2. Зюко А.Г. , Кловський Д.Д., Назаров М.В., Фінк Л.М. Теорія передачі сигналів. М: Радіо і зв'язок, 2001 р . -368 С.
3. Кнут Дональд, Грехем Роналд, Паташнік Орен Конкретна математика. Підстава інформатики - М.: Світ; Біном. Лабораторія знань, 2006. - С. 703.
4. Лідовскій В.І. Теорія інформації. - М., «Вища школа», 2002. - 120с.
5. Метрологія та радіовимірювань в телекомунікаційних системах. Підручник для ВУЗів. / В. І. Нефьодов, В.І. Халкин, Є.В. Федоров та ін - М.: Вища школа, 2001 р . - 383с.
6. Рудаков О. М. Числа Фібоначчі та простота числа ²¹²⁷ -1 / / Математичне Просвітництво, третя серія. - 2000. - Т. 4.
7. Стахов О.П. Коди золотої пропорції. -М.: Радіо та зв'язок, 1984.
8. Цапенко М.П. Вимірювальні інформаційні системи. -. - М.: Енергоатом издат, 2005. - 440С.