Область наук:

  • Математика

  • Рік видавництва: 2006


    Журнал: Известия Південного федерального університету. Технічні науки


    Наукова стаття на тему 'Алгоритм целочисленной операції ділення для мікроконтролера MSP 430'

    Текст наукової роботи на тему «Алгоритм целочисленной операції ділення для мікроконтролера MSP 430»

    ?Вважаємо, що модель (4), (5) слід застосовувати з параметрами до<3 і К-тоді вийде задовільний співвідношення складність пристрою (не більше двох умножителей) - похибка відтворення (не більше 0,5%).

    Для більш точного відтворення функції (1) і аналогічних їй равноамплітудних полиномов планується вести пошук нових способів відтворення.

    БІБЛІОГРАФІЧНИЙ СПИСОК

    1. Двайт. Таблиця інтегралів. -М .: 1982.

    2. Фролов С. С. Способи реалізації равноамплітудних полиномов // Матеріали Всеросійської науково-практичної конференції "Сучасні інформаційні технології в науці, освіті і практиці". Оренбург. 2004.

    М.І. Ледовських

    АЛГОРИТМ цілочислових операцій РОЗПОДІЛУ ДЛЯ МИКРОКОНТРОЛЛЕРА М8Р 430

    Мікроконтролер ЗАХОДІВ 430 не підтримує апаратно обробку дійсних змінних (правильних дробів і мішаних чисел). У ньому реалізується цілочисельний режим обчислень з тією особливістю, що команда ділення відсутня, а операція множення виконується прискорено завдяки наявності апаратного помножувача.

    Як показано в [1], цілочисельні арифметичні операції додавання (віднімання), множення і ділення можна задіяти для виконання відповідних операцій над речовими змінними. Однак в мікроконтролері ЗАХОДІВ 430 виконання операції ділення дійсних змінних не може у зв'язку з відсутністю її целочисленного аналога. Для усунення даної перешкоди необхідно розробити спеціальний алгоритм, що забезпечує виконання целочисленной операції ділення за допомогою наявних операцій цілочисельний арифметики..

    З метою розробки зазначеного алгоритму розглянемо операцію ділення дійсних змінних ь = х / у, для якої відомі діапазони зміни діленого х, подільника у і приватного ь відповідно | X I тш< I X I < I X I тах,

    I у I тт< I у I < I у I тах і I ь I тт<! ь !<! ь I тах. Згідно з методикою, викладеною в [1], неважко отримати целочисленную модель даної операції

    2-я (2ПХ)

    Ред = ^ '. (1)

    У

    Тут Х, У і видання - цілочисельні аналоги речових змінних х, у і ь, причому 0<| Х |<2п-1-1, 0<| У |<2п-1-1 і 0<| Комерсант |<2п-1-1, де п - розрядність цілочисельного формату даних (рис.1); 2п-4 = М'Му / Мх - вирівнюючий коефіцієнт, а МХ, Му і М'- масштаби дійсних змінних х, у і ь у вигляді ступенів числа

    2.

    п-1 п-2 1 0

    зн

    Рис.1. Формат цілочисельних даних

    У целочисленной моделі (1) виконуються наступні дії. Коефіцієнт 2П означає перенесення двійковій точки в співмножником Х на п розрядів вправо. Отже, для отримання твори 2пХ досить розташувати Х в старшій половині 2п-розрядної комірки, у якій молодша частина обнулена. Для обліку коефіцієнта 2-4 необхідно зрушити величину 2пХ на q двійкових розрядів вправо. В результаті утворюється 2п-розрядний твір 2-<1 (2пХ), формат якого наведено на рис.2. Потім виконується операція цілочисельного ділення 2п-розрядного діленого 2-<1 (2пХ) на п-розрядний дільник У, що дозволяє отримати п-розрядний приватне 7 .

    2п-1 2п-2 п-1 п п-1 п-2 1 0

    зн

    Рис.2. Формат целочисленного діленого

    Зауважимо, що цілочисельний результат ред пов'язаний з очікуваним речовим аналогом ь співвідношенням виду ь * = 7 / М', де ь * - наближене дійсне значення приватного. Виникає різниця у'= ь-ь * є похибкою виконання операції ділення дійсних змінних ь = х / у в целочисленном форматі даних.

    Розглянемо аналітичну оцінку похибки у', враховуючи дві причини її появи. По-перше, речові змінні х і у представляються в п-розрядному целочисленном форматі даних з похибками! Рх I = Дх / 2 «И XI / 2п і! Ру I = Ду / 2« I у I / 2п, де Дх і Ду - кванти цих змінних [1]. Наслідком даної обставини є трансформована похибка речового приватного п'. По-друге, целочисленное приватне видання, що отримується на виході моделі (1), має деяку похибка е7 (похибка моделі). Ця похибка перетворюється в відповідну похибку речового приватного е'за допомогою очевидного співвідношення е'= е7 / М'= е7Д' «е'I ь I / 2п-1, де Д'

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

    !у'I = Кь I +! б'I.

    Найбільш оптимальним співвідношенням між похибками п'і е'

    є наближений баланс I п'I «I е'I, який в розгорнутій формі

    виглядає наступним чином:

    1 I I | х | I I е 7 | ь |

    131р х +4 р>'1 »ти- <2>

    к1 у 2

    Розкриваючи в (2) оцінки! Рх I і | py I, отримуємо умову, що забезпечує виконання балансу похибок: е7 «1.

    Зауважимо, що умова е7 «1 отримано для ідеалізованого випадку, коли операнди х і у містять лише похибки рх і ру. Насправді до погрішностей рх і ру додаються накопичені похибки попередніх обчислень, що істотно збільшує трансформовану похибка п'. Тому умова е7 «1 в більшості випадків забезпечує баланс похибок виду! У' !>!е'I і в цьому сенсі є найбільш жорстким.

    Отримаємо алгоритм целочисленной операції ділення, що задовольняє умові е7 «1. Для простоти викладу скористаємося абстрактній операцією ділення 7 = Х / У, де 2п-2<У<2п-1-1 - п-розрядний дільник (рис.1), а 0<Х<(2п-1-1) У

    - 2п-розрядний ділене (рис.2). Наведені обмеження на дільник і ділене

    легко задовольняються на практиці. Зокрема, дільник приводиться до інтервалу 2п-2<У<2п-1-1 шляхом зсуву на необхідну кількість двійкових розрядів вліво при одночасному зсуві діленого. У даній постановці передбачається, що значення Х і У є точними, оскільки аналіз повинен проводитися без урахування трансформованої похибки.

    З огляду на архітектурні особливості мікроконтролера ЗАХОДІВ 430, зведемо операцію ділення 7 = Х / У до обчислення зворотної функції Р (У) = 22п-3 / У з наступним множенням на ділене: 7 = 2 (2п-3) (Р-Х). Для обчислення зворотної функції скористаємося ітераційним методом Ньютона [2], який забезпечує високу швидкість збіжності і реалізується за допомогою операцій додавання, віднімання і множення.

    Як відомо, метод Ньютона вельми чутливий до вибору початкового наближення. Поставимо задачу отримати алгоритм початкового наближення, який відрізняється малою трудомісткістю і прийнятною точністю. Для цього скористаємося підходом, запропонованим в [3]. Його суть полягає в тому, що зворотна функція Р (У) = 22п-3 / У апроксимується на інтервалі 2п-2<У<2п-1 по двом влучним граничним значенням Р (2п-2) = 2п-1 і Р (2п-1) = 2п-2. В результаті виходить проста інтерполяціонная формула

    Р0 (У) = 2п-1 + 2п-2 - У. (3)

    Потім методична похибка формули (3) апроксимується лінійними відрізками на двох подинтервалах 2п-2<У<2п-2 + 2п-4 і 2п-2 + 2п-4< У<2п-1 і додається до знайденого значенням Р0 (У):

    п1 п2 [2-1 (У - 2п-2), якщо У - 2п-2 < 2п-4;

    Р0 (У) = 2 + 2п-2 - У-<| (4)

    [2-2 (2п-1 - У), якщо У - 2п-2 > 2п-4.

    Аналітичний аналіз методичної похибки алгоритму (4) ЦРО показує, що її можна оцінити таким чином: | ТРО I <2п-6. Наприклад, для 8разрядного формату даних (п = 8) | ТРО I <4, тобто не більше 3% в відносних одиницях. Зауважимо, що така точність досягається за допомогою простих операцій додавання, віднімання і зсуву, які в мікроконтролері ЗАХОДІВ 430 виконуються найшвидше.

    Повну похибка алгоритму (4) ЕРО можна оцінити у вигляді суми | ЕРО | = | ЦРО | + | РРО |, де РРО - інструментальна похибка, викликана округленням дрібних величин до цілих значень, причому | РРО |<2-1 (округлення по '/ 2). Тому між похибками ТРО та РРО існує співвідношення | ЦРО I >> !РРО I, що дозволяє похибкою РРО знехтувати, тобто | ЕРО | «| ТРО I <2п-6.

    Ця величина є оцінкою похибки початкового наближення Р0.

    На рис.3 наведено графік похибки початкового наближення Р0, отриманий шляхом моделювання алгоритму (4) при п = 8 в системі Ма11а'7 / 81ті1шк6 / Р1хе ^ Рот1. Графік повністю підтверджує наведену вище оцінку похибки | ЕРО | »| ЦРО I <4.

    Використання методу Ньютона для обчислення зворотної функції Р (У) = 22п-3 / У призводить до наступним алгоритмом:

    -2п + 3 ^ / "-" 2п-3

    '' - V Г>1, 1

    (5)

    к = 1,2, ..., т,

    де Р0 - початкове наближення, що отримується з (4); т - кількість ітерацій.

    Рк = Рк-1 + 2 + 3Рк-1 (22п-3 - УРК-1),

    про

    про

    X

    3

    ф

    | _

    про

    з

    дільник У

    Рис.3. Похибка початкового наближення

    Умовою збіжності ітераційного процесу (5) є 2 "п + 21Б-Р01 <1. Так як | Б-Бо | »| єРо | <2п-6, то умова збіжності виконується.

    Методична похибка алгоритму (5) ЦРТ підпорядковується оцінці

    - Бт I < 2п-2 (2п + 2 ІБ - Бо |) 2т.

    (6)

    Вимагатимемо, щоб похибка ЦРТ задовольняла умові 1трт1<1-Тоді з (6) можна знайти количесво ітерацій т, що задовольняє цій умові при заданій розрядності формату даних п (табл.). Крім того, з (6) при відомих п і т випливає справжня оцінка методичної похибки, яка виходить однаковою для будь-якої розрядності: | ЦРТ | <2-2.

    Таблиця

    Розрядність п 8 16 32 64

    Кількість ітерацій т 1 2 3 4

    Повна похибка алгоритму (5) ЕРТ підпорядковується оцінці в вигляді суми | ЕРТ | = | ЦРТ | + | РРТ |, де РРТ - інструментальна похибка, викликана округленням дрібних величин до цілих значень. Як відомо, метод Ньютона автоматично компенсує інструментальну похибку, утворену в попередній ітерації. Отже, в розрахунок слід приймати тільки похибка РРТ, одержувану на останній ітерації, вважаючи, що попереднє наближення Рт_1 не містить інструментальну похибку. З цієї причини для похибка РРТ справедлива оцінка | РРТ |<2-1 (округлення по ^). Отже, з урахуванням | ЦРТ | <2-2, похибка алгоритму (5) ЕРТ можна оцінити таким чином: | ЕРТ | < 2-1 + 2-2 = 0,75. Дана величина є оцінкою похибки, з якою обчислюється зворотна функція Бт.

    На рис. 4 наведено графік похибки обчислення зворотної функції Бт, отриманий шляхом спільного моделювання алгоритмів (4) і (5) при п = 8 і т = 1 в системі Ма11а'7 / 81ті1тк6Мхе ^ Рот1 Графік підтверджує аналітичну оцінку похибки | БРТ | < 0,75.

    дільник У

    Рис.4. Похибка обчислення зворотної функції

    Після отримання значення зворотної функції Бт шукане приватне видання = Х / У обчислюється за формулою

    Ред = 2-2п + 3 (Бт • X) = 2-п + 1 (2-п + 2 Х) Бт. (7)

    Повну похибка формули (7) е'можна оцінити у вигляді суми | | = | ЕРТ | + | р '|, де р' - інструментальна похибка, викликана округленняприкріплюється-

    ем дрібних величин до цілих значень, причому | р '|<2-1 (округлення по '/ 2). Тому остаточна оцінка для е', з урахуванням | ЕРТ | < 0,75, має вигляд | е'| <1,25. Так як аналітична оцінка | е'| < 1,25 є завищеною, то можна зробити висновок, що поставлене вище умова е2 »1 виконується, тобто целочисленное приватне видання обчислюється з необхідною похибкою 6'.

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

    (7) при п = 8 і т = 1 в системі Ма11а'7 / 81ті1тк6Мхе ^ Рот1. Результати моделювання підтверджують аналітичну оцінку похибки И< 1,25 »1.

    Структура 81ті1шк-моделі для експериментального аналізу похибки целочисленного приватного приведена на рис.6. Тут затінений блок 8іЬ8уБ1ет є підсистемою, яка забезпечує реалізацію алгоритмів (4), (5) і (7), а решта - призначені для обчислення похибки е'. Модель запускається з т-файлу, де задається повний набір значень діленого Х від 64 до

    127У для кожного значення дільника У, який, в свою чергу, змінюється від 64 до 127 з кроком 1.

    Для значень діленого Х від 64 до 127У з кроком 1

    1.5

    0.5

    -0.5

    -1.5

    60 70 80 90 100 110 120 130

    дільник У

    Рис.5. Область розподілу похибки целочисленного приватного

    Мал. 6. 81ші11пк-модель для експериментального аналізу похибки целочисленного приватного

    Структура підсистеми 8іЬ8ує1ет приведена на рис.7. У ній всі операції множення виконуються в форматі 8x8, а операції додавання, віднімання і зсуву - в 8-розрядному форматі. Виняток становить операція віднімання в алгоритмі (5), яка виконується в 16-розрядному форматі.

    1

    0

    Оаіп4

    Мал. 7. Підсистема $ і'$ уя1еш, що реалізує алгоритм целочисленной операції

    ділення

    Алгоритми (4), (5) і (7) утворюють шуканий алгоритм целочисленной операції ділення. Даний алгоритм можна використовувати для виконання операції ділення дійсних змінних в мікроконтролері ЗАХОДІВ 430 з будь-який наперед заданою точністю (розрядністю). Слід також зазначити, що пропонований алгоритм не залежить від діапазонів зміни речових змінних і їх масштабів, що забезпечує його універсальність. Крім того, алгоритм можна використовувати для отримання наближеного приватного при обробці даних, які за своєю природою є цілочисельними.

    БІБЛІОГРАФІЧНИЙ СПИСОК

    1. Ледовських М.І. Обробка речових даних в мікроконтролерах з арифметикою фіксованою точки // Известия ТРТУ. Таганрог: 2004. №2 - (37). С. 52-58.

    2. БахваловН.С. Чисельні методи. -М .: Наука, 1973. - 631с.

    3. Ледовських М.І. Простий алгоритм обчислення малоразрядного приватного в мікропроцесорах // Матеріали Міжнародної наукової конференції "Інформаційний підхід в природничих, гуманітарних і технічних науках", Ч. 3. Таганрог. 2004. С. 49-54.


    Завантажити оригінал статті:

    Завантажити