Реферат: Коды Фибоначи. Коды Грея

Реферат

покурсу “Теория информации и кодирования ”

 

Тема:

"СПЕЦИАЛЬНЫЕ КОДЫ"

1. КОДЫ ФИБОНАЧЧИ

1.1 ЗОЛОТЫЕ ПРОПОРЦИИ

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

Например: Число p= 2pR/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.

При этом x2–x–1 = 0.Корни этого уравнения равны: x1,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) совпадает с двоичными разрядами 2n (табл.1)<sup/>.

 

Таблица1 n 1 2 3 4 5

j(n)

1 2 4 8 16 32

При р = 1 число j(n) совпадает с обычным рядом Фибоначчи:

1, 1, 2, 3, 5, 8, ...

При р = /> числоj(n)= 1 для любого n ³равно:

1, 1, 1, 1, 1, 1, 1, 1, ...

 

1.3 КОДЫ ФИБОНАЧЧИ

 

Любое натуральное число N можнопредставить с помощью p-чисел Фибоначчи

/> (4)

где: ai Î{0, 1} — двоичная цифра i-го разряда; jp(i) — вес i-го разряда;

Любое натуральное число N можнопредставить также следующим способом:

/> (5)

Такое представление чисел Nназывается p-кодом Фибоначчи. Каждому p<sub/>Î{0, 1, 2, …,¥} соответствует свой код, т. е. их число бесконечно.

При p = 0 p -код Фибоначчисовпадает с двоичным кодом.

Для 1-кода Фибоначчи кодовые комбинацииимеют вид:

Таблица 2