Щербаков а. Н., Проскурін м. П., Грушко с. С. Прикладна теорія цифрових автоматів

• Название: Щербаков а. Н., Проскурін м. П., Грушко с. С. Прикладна теорія цифрових автоматів
• Анкор: Ukr1_PTTsA_kl_ch1_10-02-2010.doc
• Дата: 13.02.2018
• Размер: 2.54 Mb.
• Имя файла: Ukr1_PTTsA_kl_ch1_10-02-2010.doc
• Тип: Протокол; #15521
• страница: 3 из 26

2 СИСТЕМИ ЧИСЛЕННЯ

2.1 Огляд деяких систем числення

Сам процес числення (нумерація)  сукупність певних прийомів (правил, алгоритмів) представлення натуральних чисел. Систем числення існує багато.

У будь-якій системі числення прийняті деякі символи (знаки, слова) для позначення певних чисел, ці знаки називають базовими (вузловими). Наприклад, в 10-ій системі базовими є знаки (зображення) 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, що позначають цілі натуральні числа від 0 до 9 і дроби за допомогою коми (крапки).

Решта чисел уявного діапазону числової вісі мають назву алгоритмічні і створюються в результаті виконання дій за певними правилами над базовими числами (10, 123, 543). Тому системи числення відрізняються одна від одної вибором базових (вузлових) чисел і способами утворення алгоритмічних. При письмовому позначенні вони відрізняються характером використаних числових знаків і принципами їх запису. Наприклад, у стародавніх вавілонян базовими були числа 1,10,60; у племені маорі (Нова Зеландія)  1, 11, 112, 113; у римській системі числення вузловими були числа 1, 5, 10, 50, 100, 500, 1000, які позначалися знаками І, V, X, L, C, D, M: приклад MCMXCVII - 1997.

Системи числення, в яких алгоритмічні числа утворюються складанням вузлових, називаються адитивними. Наприклад, в стародавньоєгипетській системі числення числа 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 19, 40 позначалися відповідно:


|, ||, |||, ||||, ||| ||| |||| |||| ||| |||

||, |||, |||, ||||, ||| ∩, ∩ ||| ∩∩∩∩.

|||, |||,


У римській системі числення числа виходять шляхом складання і віднімання вузлових.

У сучасних числах (в т.ч. європейських, українській і російській мовах, ін.) застосований адитивно-мультиплікативний спосіб. В деяких країнах були прийняті алфавітні системи числення  наприклад, греки, стародавні слов’яни, ін. (цифри від 1 до 9 зображалися буквами алфавіту з межею зверху).

Будь-яка призначена для практичних розрахунків система числення повинна забезпечувати:

- однозначність відображення числа;

- представлення всіх чисел в діапазоні числової осі;

- простоту запису чисел і виконуваних операцій над ними;

- систему правил запису і читання чисел.

Системи числення діляться на позиційні і непозиційні.

Позиційна система числення - система, в якій значення базових знаків залежить від їх місцеположення в числі, розрядності. (Тобто 0…9 в розряді одиниць не дорівнює 0…9 в розряді десятків, сотень, тисяч, ін.  бо прийнято, що вага сусідніх розрядів таких чисел різниться на порядок).

Непозиційна система числення- система, в якій значення базових знаків не залежить від їх місцеположення в числі, розрядності.

Принцип побудови таких систем полягає у виборі базових знаків і при читанні (або запису) проводяться операції складання (іноді і віднімання). Наприклад: Робінзон Крузо застосував непозиційну систему числення для підраховування діб. Базовий знак  вертикальна риска, які він складав і отримував числа. Ця система неефективна з двох причин:

- запис числа може виявитися довгим і незручним;

- для виконання підрахунків необхідно використовувати іншу систему.

Проте вона дуже проста.

Римську систему числення можна назвати частково позиційною, хоча вона вважається непозиційною системою. Так, наприклад, в числах LX і XL знак X (10) приймає два значення ±10 і залежить від свого місцеположення відносно L (справа чи зліва).

2.2 Система залишкових класів

Однією з непозиційних систем числення, розробленою спеціально для застосування в спеціалізованих ЕОМ, є система в залишкових класах (СЗК).

Ідейне коріння СЗК пов’язане з працями Ейлера, Гауса і Чебишева з теорії порівнянь. Значний внесок в розвиток СЗК внесли чеські вчені математики М. Валах і А. Свобода, що працювали над представленням чисел у вигляді сукупності ненегативних вирахувань по групі взаємнопростих основ [1-21].

Хай необхідно записати число N, задане в 10-ій системі в системі СЗК.

Кінцеву множину позитивних цілих чисел, взаємно простих між со-бою, назвемо базисом основ системи числення в залишкових класах [14] .

Під системою числення в залишкових класах будемо розуміти таку систему, в якій ціле число представляється у вигляді набору залишків (вирахувань) по вибраних основах р_i.

Тоді число N в СЗК буде записано як: (2.1)

_{де (2.2)}

тобто a_i – є відображення числа N у вигляді позитивного залишку від ділення N націло на основу Р_i.

При цьому буде завжди справедлива нерівність a_i<p_i. (де і=1,2…n).

У відомій з теорії чисел першій і другій функціональній теоремі Гауса, доведено, що якщо числа р_iвзаємно прості між собою, то опис {a₁, a₂, a_n}, що представляє N, є єдиним.

Нагадаємо, що взаємно простими числами називають числа, що мають найменший загальний дільник (НЗД), що дорівнює 1. Наприклад, 15 і 22 є взаємно прості числа (оскільки НЗД рівний 1).

Приклад. Нехай вибрані основи СЗК: р={3,5,7}. Представимо десяткове число N=67 у СЗК.

Рішення. Знайдемо залишки згідно виразу 2.2







Отже, число 67 записується в СЗК як {1,2,4}, або в двійковій  {001,010,100}.

Діапазон чисел, що представляються, дорівнює:

Зворотний переклад числа з СЗК в десяткову систему проводиться за формулою:

_(2.3)

де r  ранг, що приймає значення 0, 1, 2, … так, щоб права частина виразу 2.3 була менше R;

B_i  ортогональний базис, що визначає при виборі базису СЗК.



де k_i  ціле позитивне число (k_i=1, 2, …, р_і1), при цьому k_iвибирається таким, щоб залишок від ділення В_і на р_і дорівнював одиниці (тобто вага базису k_i вибирається виходячи з рівності):

_(2.4)

Приклад. Визначимо для СЗК з основами {3,5,7} ортогональні базиси B_i та переведемо число {1,2,4} в десяткову систему.

;

(для р₁=3 умова 2.4 виконується при k=2),

;

(для р₂ =5 умова 2.4 виконується при k=1),

;

(для р₃ =7 умова 2.4 виконується при k=1), тоді N = (a₁B₁+a₂B₂+a₃B₃)  r  R = (170+221+415)  r 105 =1721105=67.

Запишемо число 67 в двійковій системі 1000011 і в СЗК 001_ 010_ 100. Цифри СЗК в кожному розряді вирахувань по-перше, незалежні один від одного і не залежать від позиції, а лише залежать від базису; по-друге, кожен розряд вирахувань несе інформацію про число в цілому. Ця властивість СЗК використовується для відновлення спотвореної інформації при передачі по лінії зв’язку.