Перетворення з загальними множниками

1. Пристрій для виконання перетворень даних, який містить: першу логіку виконання множення першої групи щонайменше з однієї величини даних на першу групу щонайменше з однієї раціональної двійкової константи, яка апроксимує першу групу щонайменше з однієї ірраціональної константи, масштабованої першим загальним множником, причому кожна раціональна двійкова константа є раціональним числом з двійковим знаменником; і другу логіку для виконання множення другої групи щонайменше з однієї величини даних на другу групу щонайменше з однієї раціональної двійкової константи, яка апроксимує другу групу щонайменше з однієї ірраціональної константи, масштабованої другим загальним множником, причому перша і друга групи щонайменше з однієї величини даних мають різні розміри. 2. Пристрій за п. 1, який додатково містить: третю логіку для виконання множення третьої групи щонайменше з однієї величини даних на третю групу щонайменше з однієї раціональної двійкової константи, яка апроксимує третю групу щонайменше з однієї ірраціональної константи, масштабованої третім загальним множником. 3. Пристрій за п. 1, в якому друга група щонайменше з однієї величини даних в два рази більше першої групи щонайменше з однієї величини даних. 4. Пристрій за п. 1, в якому перша група щонайменше з однієї величини даних містить дві величини даних, а друга група щонайменше з однієї величини даних містить чотири величини даних. 2 (19) 1 3 13. Пристрій за п. 11, в якому перший і другий загальні множники додатково вибирають на основі щонайменше одного показника точності для результатів, згенерованих з множення. 14. Пристрій за п. 1, в якому перший загальний множник вибирають за допомогою визначення числа логічних і арифметичних операцій, необхідних для множення першої групи щонайменше з однієї величини даних на різні можливі величини для першої групи щонайменше з однієї раціональної двійкової константи, одержаної за допомогою різних можливих величин першого загального множника. 15. Пристрій за п. 1, в якому для множення величини даних в першій групі на раціональну двійкову константу в першій групі перша логіка генерує послідовність проміжних величин на основі величини даних, причому щонайменше одну проміжну величину в послідовності генерують на основі щонайменше однієї іншої проміжної величини в послідовності, і надає одну проміжну величину в послідовності як вихідну величину для множення величини даних на раціональну двійкову константу. 16. Пристрій за п. 1, в якому перша і друга логіки виконують множення для лінійного перетворення. 17. Пристрій за п. 16, який додатково містить: третю логіку для виконання щонайменше однієї операції метелика на основі вихідних даних першої і другої логік, щоб згенерувати результати для лінійного перетворення. 18. Пристрій за п. 1, в якому перша і друга логіки виконують множення для дискретного косинусного перетворення (DCT). 19. Пристрій за п. 1, в якому перша і друга логіки виконують множення для зворотного дискретного косинусного перетворення (IDCT). 20. Пристрій за п. 1, в якому перша і друга логіки виконують множення для 8-ми точкового дискретного косинусного перетворення (DCT) або 8-ми точкового зворотного дискретного косинусного перетворення (IDCT). 21. Пристрій для виконання перетворень даних, який містить: першу логіку для виконання множення першої групи з двох величин даних на першу групу з двох раціональних двійкових констант, яка апроксимує першу групу щонайменше з однієї ірраціональної константи, масштабованої першим загальним множником, причому кожна раціональна двійкова константа є раціональним числом з двійковим знаменником; і другу логіку для виконання множення другої групи з чотирьох величин даних на другу групу з чотирьох раціональних двійкових констант, яка апроксимує другу групу щонайменше з однієї ірраціональної константи, масштабованої другим загальним множником. 22. Спосіб виконання перетворень даних, який містить етапи, на яких: виконують, за допомогою процесора системи обробки відео, множення першої групи щонайменше з однієї величини даних, пов'язаних з відео, на першу групу щонайменше з однієї раціональної двійкової константи, яка апроксимує першу групу щонайменше з однієї ірраціо 92780 4 нальної константи, масштабованої першим загальним множником, причому кожна раціональна двійкова константа є раціональним числом з двійковим знаменником; і виконують, за допомогою процесора системи обробки відео, множення другої групи щонайменше з однієї величини даних, пов'язаних з відео, на другу групу щонайменше з однієї раціональної двійкової константи, яка апроксимує другу групу щонайменше з однієї ірраціональної константи, масштабованої другим загальним множником, причому перша і друга групи щонайменше з однієї величини даних мають різні розміри. 23. Спосіб за п. 22, який додатково містить етап, на якому: виконують множення третьої групи щонайменше з однієї величини даних на третю групу щонайменше з однієї раціональної двійкової константи, яка апроксимує третю групу щонайменше з однієї ірраціональної константи, масштабованої третім загальним множником. 24. Спосіб за п. 22, в якому виконання множення першої групи щонайменше з однієї величини даних включає етапи, на яких для множення величини даних в першій групі на раціональну двійкову константу в першій групі: генерують послідовність проміжних величин на основі величини даних, причому щонайменше одну проміжну величину в послідовності генерують на основі щонайменше однієї іншої проміжної величини в послідовності, і надають одну проміжну величину в послідовності як вихідну величину для множення величини даних на раціональну двійкову константу. 25. Спосіб за п. 22, в якому виконання множення другої групи щонайменше з однієї величини даних включає етап, на якому виконують множення величини даних у другій групі на першу і другу раціональні двійкові константи у другій групі на основі однієї послідовності проміжних величин. 26. Пристрій для виконання перетворень даних, який містить: засіб для виконання множення першої групи щонайменше з однієї величини даних на першу групу щонайменше з однієї раціональної двійкової константи, яка апроксимує першу групу щонайменше з однієї ірраціональної константи, масштабованої першим загальним множником, причому кожна раціональна двійкова константа є раціональним числом з двійковим знаменником; і засіб для виконання множення другої групи щонайменше з однієї величини даних на другу групу щонайменше з однієї раціональної двійкової константи, яка апроксимує другу групу щонайменше з однієї ірраціональної константи, масштабованої другим загальним множником, причому перша і друга групи щонайменше з однієї величини даних мають різні розміри. 27. Пристрій за п. 26, який додатково містить: засіб для виконання множення третьої групи щонайменше з однієї величини даних на третю групу щонайменше з однієї раціональної двійкової константи, яка апроксимує третю групу щонайменше з однієї ірраціональної константи, масштабованої третім загальним множником. 5 28. Пристрій за п. 26, в якому засіб для виконання множення першої групи щонайменше з однієї величини даних містить для множення величини даних в першій групі на раціональну двійкову константу в першій групі: засіб для генерації послідовності проміжних величин на основі величини даних, причому щонайменше одну проміжну величину в послідовності генерують на основі щонайменше однієї іншої проміжної величини в послідовності, і засіб для надання однієї проміжної величини в послідовності як вихідної величини для множення величини даних на раціональну двійкову константу. 29. Пристрій за п. 26, в якому засіб для виконання множення другої групи щонайменше з однієї величини даних містить засіб для виконання множення величини даних у другій групі на першу і другу раціональні двійкові константи у другій групі на основі однієї послідовності проміжних величин. 30. Пристрій для виконання перетворень даних, який містить: першу логіку для прийому щонайменше однієї величини даних; і другу логіку для виконання множення щонайменше однієї величини даних на щонайменше одну раціональну двійкову константу, яка апроксимує щонайменше одну ірраціональну константу, масштабовану загальним множником, причому кожна раціональна двійкова константа є раціональним числом з двійковим знаменником, причому загальний множник вибирають на основі числа логічних і арифметичних операцій, необхідних для множення щонайменше однієї величини даних на щонайменше одну раціональну двійкову константу. 31. Пристрій за п. 30, в якому логічні і арифметичні операції містять операції зсуву і додавання. 32. Пристрій за п. 30, в якому загальний множник додатково вибирають на основі щонайменше одного показника точності для результатів, згенерованих з множення щонайменше однієї величини даних на щонайменше одну раціональну двійкову константу. 33. Пристрій за п. 30, в якому для множення величини даних на раціональну двійкову константу друга логіка генерує послідовність проміжних величин на основі величини даних, причому щонайменше одну проміжну величину в послідовності генерують на основі щонайменше однієї іншої проміжної величини в послідовності, і надає одну проміжну величину в послідовності як вихідну величину для множення величини даних на раціональну двійкову константу. 34. Пристрій за п. 30, в якому число логічних і арифметичних операцій визначають за допомогою виконання множення щонайменше однієї величини даних на щонайменше одну раціональну двійкову константу з використанням проміжних результатів, щоб згенерувати щонайменше одну вихідну величину для множення. 35. Спосіб виконання перетворень даних, який включає етапи, на яких: приймають, за допомогою процесора системи обробки відео, щонайменше одну величину даних, пов'язаних з відео; і 92780 6 виконують, за допомогою процесора системи обробки відео, множення щонайменше однієї величини даних на щонайменше одну раціональну двійкову константу, яка апроксимує щонайменше одну ірраціональну константу, масштабовану загальним множником, причому кожна раціональна двійкова константа є раціональним числом з двійковим знаменником, причому загальний множник вибирають на основі числа логічних і арифметичних операцій, необхідних для множення щонайменше однієї величини даних на щонайменше одну раціональну двійкову константу. 36. Спосіб за п. 35, в якому логічні і арифметичні операції включають операції зсуву і додавання. 37. Спосіб за п. 35, в якому виконання множення включає етапи, на яких для множення величини даних на раціональну двійкову константу: генерують послідовність проміжних величин на основі величини даних, причому щонайменше одну проміжну величину в послідовності генерують на основі щонайменше однієї іншої проміжної величини в послідовності, і надають одну проміжну величину в послідовності як вихідну величину для множення величини даних на раціональну двійкову константу. 38. Пристрій для виконання перетворень даних, який містить: засіб для прийому щонайменше однієї величини даних; і засіб для виконання множення щонайменше однієї величини даних на щонайменше одну раціональну двійкову константу, яка апроксимує щонайменше одну ірраціональну константу, масштабовану загальним множником, причому кожна раціональна двійкова константа є раціональним числом з двійковим знаменником, причому загальний множник вибирають на основі числа логічних і арифметичних операцій, необхідних для множення щонайменше однієї величини даних на щонайменше одну раціональну двійкову константу. 39. Пристрій за п. 38, в якому логічні і арифметичні операції містять операції зсуву і додавання. 40. Пристрій за п. 38, в якому засіб для виконання множення містить для множення величини даних на раціональну двійкову константу: засіб для генерації послідовності проміжних величин на основі величини даних, причому щонайменше одну проміжну величину в послідовності генерують на основі щонайменше однієї іншої проміжної величини в послідовності, і засіб для надання однієї проміжної величини в послідовності як вихідної величини для множення величини даних на раціональну двійкову константу. 41. Машиночитаний носій, що містить: код для того, щоб викликати прийом комп'ютером щонайменше однієї величини даних, пов'язаних з відео; і код для того, щоб викликати виконання комп'ютером множення щонайменше однієї величини даних на щонайменше одну раціональну двійкову константу, яка апроксимує щонайменше одну ірраціональну константу, масштабовану загальним множником, причому кожна раціональна двійкова константа є раціональним числом з двійковим 7 92780 8 знаменником, причому загальний множник вибирають на основі числа логічних і арифметичних операцій, необхідних для множення щонайменше однієї величини даних на щонайменше одну раціональну двійкову константу. 42. Машиночитаний носій, що містить: код для того, щоб викликати виконання комп'ютером множення першої групи щонайменше з однієї величини даних, пов'язаних з відео, на першу групу щонайменше з однієї раціональної двійкової константи, яка апроксимує першу групу щонайменше з однієї ірраціональної константи, масштабованої першим загальним множником, причому кожна раціональна двійкова константа є раціональним числом з двійковим знаменником; і код для того, щоб викликати виконання комп'ютером множення другої групи щонайменше з однієї величини даних, пов'язаних з відео, на другу групу щонайменше з однієї раціональної двійкової константи, яка апроксимує другу групу щонайменше з однієї ірраціональної константи, масштабованої другим загальним множником, причому перша і друга групи щонайменше з однієї величини даних мають різні розміри. 43. Машиночитаний носій за п. 42, який додатково містить: код для того, щоб викликати виконання комп'ютером множення третьої групи щонайменше з однієї величини даних на третю групу щонайменше з однієї раціональної двійкової константи, яка апроксимує третю групу щонайменше з однієї ірраціональної константи, масштабованої третім загальним множником. Дана заявка вимагає пріоритет попередньої заявки США №60/758,464, поданої 11 січня 2006p., озаглавленої "Ефективні здійснення без множення масштабованого дискретного косинусного перетворення (DCT) і зворотного дискретного косинусного перетворення (ГОСТ)", правовласником якої є заявник даного винаходу, і включеної в цей опис як посилання. Дане розкриття загалом належить до обробки і, більш конкретно, до способів, призначених для виконання перетворень даних. Перетворення звичайно використовують, щоб конвертувати дані з однієї області визначення в іншу область визначення. Наприклад, дискретне косинусне перетворення (DCT) звичайно використовують, щоб перетворювати дані з просторової області визначення в частотну область визначення, а зворотне дискретне косинусне перетворення (ГОСТ) звичайно використовують, щоб перетворювати дані з частотної області визначення в просторову область визначення. DCT широко використовують для стиснення зображення/відео, щоб виконати скасування просторової кореляції блоків елементів зображення (пікселів) в зображеннях або кадрах відео. Результуючі коефіцієнти перетворення звичайно в значно меншій мірі залежать один від одного, що робить ці множники більш придатними для квантування і кодування. DCT також виявляє властивість ущільнення енергії, яке є можливістю перетворювати більшу частину енергії блока пікселів тільки в невелике число (звичайно малого порядку) коефіцієнтів перетворення. Ця властивість ущільнення енергії може спрощувати схему алгоритмів кодування. Перетворення, такі як DCT і IDСТ, можуть бути виконані відносно великої кількості даних. Отже, бажано виконувати перетворення як можна ефективніше. Крім того, бажано виконувати обчислення для перетворень з використанням простого апаратного забезпечення, для того щоб зменшити вартість і складність. Внаслідок цього в даній галузі техніки є потреба в способах, щоб ефективно виконувати перетворення відносно даних. У даній заявці описані способи, призначені для ефективного виконання перетворень відносно даних. Відповідно до одного аспекту пристрій виконує множення першої групи щонайменше з однієї величини даних на першу групу щонайменше з однієї раціональної двійкової константи, яка апроксимує першу групу щонайменше з однієї ірраціональної константи, масштабованої за допомогою першого загального множника. Пристрій додатково виконує множення другої групи щонайменше з однієї величини даних на другу групу щонайменше з однієї раціональної двійкової константи, яка апроксимує другу групу щонайменше з однієї ірраціональної константи, масштабованої за допомогою другого загального множника. Кожна раціональна двійкова константа є раціональним числом з двійковим знаменником. Перша і друга групи щонайменше з однієї величини даних мають різні розміри. Наприклад, перша група може включати в себе дві величини даних, а друга група може включати в себе чотири величини даних. Відповідно до іншого аспекту пристрій виконує множення щонайменше однієї величини даних на щонайменше одну раціональну двійкову константу, яка апроксимує щонайменше одну ірраціональну константу, масштабовану за допомогою загального множника. Загальний множник вибирають на основі числа логічних і арифметичних операцій, призначених для множення щонайменше однієї величини даних на щонайменше одну раціональну двійкову константу. Логічні і арифметичні операції можуть містити операції зсуву, віднімання і додавання. Загальні множники додатково можуть бути вибрані на основі точності результатів. Різні аспекти і ознаки розкриття описані більш детально нижче. Фіг.1 зображує граф-схему 8-ми точкового IDCT. Фіг.2 зображує граф-схему 8-ми точкового DCT. 9 Фіг.3 зображує граф-схему 8-ми точкового IDCT із загальними множниками. Фіг.4 зображує граф-схему 8-ми точкового DCT із загальними множниками. Фіг.5 зображує довідкову таблицю, яка зберігає номери операцій для множення на різні величини раціональної двійкової константи. Фіг.6 зображує блок-схему двовимірного (2D) IDCT. Фіг.7 зображує блок-схему системи кодування і декодування зображення/відео. Фіг.8 зображує блок-схему системи кодування. Фіг.9 зображує блок-схему системи декодування. Способи, описані в даній заявці, можуть бути використані для різних типів перетворень, таких як DCT, IDСТ, дискретне перетворення Фур'є (DFT), зворотне DFT (IDFT), модульоване перетворення з перекриттям (MLT), зворотне MLT, модульоване комплексне перетворення з перекриттям (MCLT), зворотне MCLT і т.д. Способи також можуть бути використані для різних застосувань, таких як обробка зображення, відео і аудіо, зв'язок, обчислення, передачі даних по мережі, зберігання даних, графіка і т.д. Звичайно способи можуть бути використані для будь-яких застосувань, які використовують перетворення. Для пояснення способи описані нижче для DCT і IDCT, які звичайно використовують при обробці зображення і відео. Одновимірне (1D) N-точкове DCT і 1D Nточкове IDСТ типу II можуть бути визначені таким чином: c(k ) N 1 (2n 1) k Рівняння (1) X[k ] x[n] cos 2 2N n 0 N 1 c(k ) (2n 1) k Рівняння (2) x[n] X[k ] cos 2 2N k 0 1/ 2 if k 0 1 в іншому випадку х[n] - 1D функція просторової області визначення, а Х[k] - 1D функція частотної області визначення. 1D DCT в рівнянні (1) оперує N величинами просторової області з х[0] по x[N-1] і генерує N коефіцієнтів перетворення з Х[0] по X[N-1]. 1D IDСТ в рівнянні (2) оперує N коефіцієнтами перетворення і генерує N величин просторової області визначення. DCT типу II є одним типом перетворення, і його звичайно вважають одним з найбільш ефективних перетворень серед декількох перетворень ущільнення енергії, запропонованих для стиснення зображення/відео. 1D DCT може бути використано для 2D DCT, як описано нижче. Подібним чином, 1D IDCT може бути використано для 2D IDCT. При декомпозиції 2D DCT/IDCT в каскад 1D DCT/IDCT ефективність 2D DCT/IDCT залежить від ефективності 1D DCT/IDCT. Звичайно 1D DCT і 1D IDCT можуть бути виконані відносно будь-якого розміру вектора, a 2D DCT і 2D IDCT можуть бути виконані відносно будь-якого розміру блока. Однак, DCT 8×8 і IDCT де c(k ) 92780 10 8×8 звичайно використовують для обробки зображення і відео, коли N дорівнює 8. Наприклад, DCT 8×8 і IDCT 8×8 використовують як стандартні компонувальні блоки в різних стандартах кодування зображення і відео, таких як JPEG, MPEG-1, MPEG-2, MPEG-4 (Р.2), Н.261, Н.263 і т.д. 1D DCT і 1D IDCT можуть бути здійснені в їх вихідних формах в рівняннях (1) і (2), відповідно. Однак, суттєве зменшення обчислювальної складності може бути реалізоване за допомогою знаходження факторизацій, що дає в результаті як можна менше число множень і додавань. Факторизація для перетворення може бути представлена за допомогою граф-схеми, яка вказує конкретні операції, виконувані для цього перетворення. Фіг.1 зображує граф-схему 100 типової факторизації 8-ми точкового IDCT. У граф-схемі 100 кожне додавання представлене за допомогою символу " ", а кожне множення представлене прямокутником. Кожне додавання підсумовує або віднімає дві вхідні величини і надає вихідну величину. Кожне множення множить вхідну величину на константу перетворення, зображену всередині прямокутника, і надає вихідну величину. Факторизація на Фіг.1 має шість множень на наступні постійні множники: С /4=cos( /4) 0.707106781, С3 /8=cos(3 /8) 0.382683432 і S3 /8=sin(3 /8) 0.923879533. Граф-схема 100 приймає вісім масштабованих коефіцієнтів перетворення з А0·Х[0] і Α7·Χ[7], виконує 8-ми точкове IDСТ відносно цих множників і генерує вісім вихідних вибірок з х[0] по х[7]. З А0 по А7 є масштабними множниками, і їх задають таким чином: 1 A0 0.3535533906 , 2 2 cos( 7 / 16) A1 0.4499881115 , 2 sin(3 / 8) 2 A2 A3 A4 A5 A6 cos( / 8) 0.6532814824 , 2 cos( 5 / 16) 0.2548977895 , 2 2 cos( 3 / 8) 1 0.3535533906 , 2 2 cos( 3 / 16) 1.2814577239 , 2 2 cos( 3 / 8) cos( 3 / 8) 0.2705980501 , 2 cos( / 16) A7 0.3006724435 . 2 2 sin(3 / 8) Граф-схема 100 включає в себе деяке число операцій метелика. Операція метелика приймає дві вхідні величини і генерує дві вихідні величини, де одна вихідна величина є сумою двох вхідних величин, а інша вихідна величина є різницею двох вхідних величин. Наприклад, операція метелика відносно вхідних величин Α0·Χ[0] і А4·Х[4] генерує вихідну величину Α0·Χ[0]+Α4·Χ[4] для верхньої гілки 11 і вихідну величину Α0·Χ[0]-Α4·Χ[4] для нижньої гілки. Фіг.2 зображує граф-схему 200 типової факторизації 8-ми точкового DCT. Граф-схема 200 приймає вісім вхідних вибірок з х[0] по х[7], виконує 8-ми точкове DCT відносно цих вхідних вибірок і генерує вісім масштабованих коефіцієнтів перетворення з 8А0·Х[0] по 8А7·Х[7]. Масштабні множники з А0 по А7 задані вище. Факторизація на Фіг.2 має шість множень на постійні множники 1/С /4, 2С3 /8 і 2S3 /8. Граф-схеми для IDCT і DCT на Фіг.1 і 2 є подібними і включають в себе множення, по суті, на однакові постійні множники (з різницею на 1/2). Така подібність може бути вигідною для реалізації DCT і IDСТ в інтегральній схемі. Зокрема, подібність може дати можливість економії площі кремнію або кристала, щоб здійснити операції метелика і множення з константами перетворення, які використовуються, як в прямому, так і в зворотному перетворенні. Факторизація, зображена на Фіг.1, дає в результаті в загальній складності 6 множень і 28 додавань, яких суттєво менше, ніж число множень і додавань, необхідних для прямого обчислення рівняння (2). Факторизація, зображена на Фіг.2, також дає в результаті в загальній складності 6 множень і 28 додавань, яких суттєво менше, ніж число множень і додавань, необхідних для прямого обчислення рівняння (1). Факторизація на Фіг.1 виконує поворот площини відносно двох проміжних змінних з 2С3 /8 і 2S3 /8. Факторизація на Фіг.2 виконує поворот площини відносно двох проміжних змінних з 2С3 /8 і 2S3 /8. Поворот площини досягається за допомогою множення проміжної змінної, як на синус, так і на косинус, наприклад, cos(3 /8) sin(3 /8) на Фіг.1. Множення для повороту площини можуть бути ефективно виконані з використанням способів обчислень, описаних нижче. Фіг.1 і Фіг.2 зображають типові факторизації 8ми точкового IDСТ і 8-ми точкового DCT, відповідно. Ці факторизації призначені для масштабованого IDCT і масштабованого DCT, де "масштабований" належить до масштабування коефіцієнтів перетворення з Х[0] по Х[7] за допомогою відомих масштабних множників з А0 по А7, відповідно. Інші факторизації також одержані за допомогою використання перетворень в інші відомі швидкі алгоритми, такі як алгоритм DFT Кулі-Тукі, або за допомогою застосування систематичних процедур факторизації, таких як децимація за часом або децимація за частотою. Звичайно факторизація зменшує число множень, але не виключає їх. Множення на Фіг.1 і Фіг.2 виконують на ірраціональні константи, що представляють синус і косинус різних кутів, які є кратними /8 для 8-ми точкових DCT і IDCT. Ірраціональна константа є константою, яка не є відношенням двох цілих. Множення на ірраціональні константи може бути більш ефективно виконане в цілочисловій арифметиці з фіксованою точкою, коли кожну ірраціональну константу апроксимують за допомогою раціональної двійкової константи. Раціональна двійкова константа є раціональною константою з 92780 12 двійковим знаменником і має вигляд с/2b , де b і с цілі і b>0. Множення цілої змінної на раціональну двійкову константу може бути виконане за допомогою логічних і арифметичних операцій, як описано нижче. Число логічних і арифметичних операцій залежить від способу, за допомогою якого виконують обчислення, а також від величини раціональної двійкової константи. У одному аспекті загальні множники використовують для того, щоб зменшити загальне число операцій для перетворення і/або щоб збільшити точність результатів перетворень. Загальний множник є константою, яку застосовують до однієї або більше проміжних змінних в перетворенні. Проміжна змінна також може бути згадана як величина даних і т.д. Загальний множник може бути поглинений однією або більше константами перетворення, а також може бути обчислений за допомогою зміни одного або більше масштабних множників. Загальний множник може поліпшити апроксимацію однієї або більше (ірраціональних) констант перетворення за допомогою однієї або більше раціональних двійкових констант, що може потім дати в результаті менше загальне число операцій і/або підвищену точність. Звичайно будь-яке число загальних множників може бути використане для перетворення, і кожний загальний множник може бути застосований до будь-якого числа проміжних змінних в перетворенні. У одній конструкції множину загальних множників використовують для перетворення і застосовують до множини груп проміжних змінних різних розмірів. У іншій конструкції множину загальних множників застосовують до множини груп проміжних змінних одного і того ж розміру. Фіг.3 зображує граф-схему 300 8-ми точкового IDCT із загальними множниками. Граф-схема 300 використовує ту ж саму факторизацію, що і графсхема 100 на Фіг.1. Однак граф-схема 300 використовує два загальних множники для двох груп проміжних змінних. Перший загальний множник F1 застосовують до першої групи з двох проміжних змінних X1 і Х2, яку генерують на основі коефіцієнтів перетворення Х[2] і Х[6]. Перший загальний множник F1 множать на Х1, поглинають за допомогою константи перетворення C /4 і розраховують за допомогою зміни масштабних множників А2 і А6. Другий загальний множник F2 застосовують до другої групи з чотирьох проміжних змінних з Х3 по Х6, яку генерують на основі коефіцієнтів перетворення Х[1], Х[3], Х[5] і Х[7]. Другий загальний множник F2 множать на Х4, поглинають за допомогою констант перетворення C /4, С3 /8 і S3 /8 і розраховують за допомогою зміни масштабних множників А1, А3, А5 і А7. Перший загальний множник F1 може бути апроксимований за допомогою раціональної двійкової константи α1, яка може бути помножена на Х1, щоб одержати апроксимацію добутку X1·F1. Масштабований множник перетворення F1·C /4 може бути апроксимований за допомогою раціональної двійкової константи βΐ5 яка може бути помножена на Х2, щоб одержати апроксимацію добутку X2·F1·C /4. Змінений масштабний множник A2/F1 може бути застосований до коефіцієнта перетво 13 рення Х[2]. Змінений масштабний множник A6/F1 може бути застосований до коефіцієнта перетворення Х[6]. Другий загальний множник F2 може бути апроксимований за допомогою раціональної двійкової константи α2, яка може бути помножена на Х4, щоб одержати апроксимацію добутку X4·F2. Масштабований множник перетворення F2·C /4 може бути апроксимований за допомогою раціональної двійкової константи β2, яка може бути помножена на Х3, щоб одержати апроксимацію добутку Х3·F2·C /4. Масштабований множник перетворення F2·С3 /8 може бути апроксимований за допомогою раціональної двійкової константи 2, а масштабований множник перетворення F2·S3 /8 може бути апроксимований за допомогою раціональної двійкової константи 2 Раціональна двійкова константа 2, може бути помножена на Х5, щоб одержати апроксимацію добутку X5·F2·С3 /8, a також на Х6, щоб одержати апроксимацію добутку X6·F2·С3 /8. Раціональна двійкова константа 2, може бути помножена на Х5, щоб одержати апроксимацію добутку X5·F2·S3 /8, а також на Х6, щоб одержати апроксимацію добутку X6·F2·S3 /8. Змінені масштабні множники A1/F2, А3/F2, A5/F2 і Α7/F2 можуть бути застосовані до коефіцієнтів перетворення Х[1], Х[3], Х[5] і Х[6], відповідно. Шість раціональних двійкових констант α1, β1, α2, β2, 2 і 2 можуть бути визначені для шести констант таким чином: α1 F1, β1 F1·cos( /4), α2 F2, β2 F2·cos( /4), 2 F2·cos(3 /8) i Рівняння (3) 2 F2·sin(3 /8). Фіг.4 зображує граф-схему 400 8-ми точкового DCT із загальними множниками. Граф-схема 400 використовує ту ж саму факторизацію, що і графсхема 200 на Фіг.2. Однак, граф-схема 400 використовує два загальних множники для двох груп проміжних змінних. Перший загальний множник Fa застосовують до першої групи з двох проміжних змінних Ха і Хb, яку використовують, щоб генерувати коефіцієнти перетворення Х[2] і Х[6]. Перший загальний множник Fa множать на Ха, поглинають за допомогою константи перетворення 1/С /4 і обчислюють за допомогою зміни масштабних множників А2 і А6. Другий загальний множник Fb застосовують до другої групи з чотирьох проміжних змінних з Хо по Xf, яку використовують, щоб генерувати коефіцієнти перетворення Х[1], Х[3], Х[5] і Х[7]. Другий загальний множник Fb множать на Xd, поглинають за допомогою констант перетворення 1/С /4, 2С3 /8 і 2S3 /8 і розраховують за допомогою зміни масштабних множників А1, A3, A5 і А7. Перший загальний множник Fa може бути апроксимований за допомогою раціональної двійкової константи αа, яка може бути помножена на Ха, щоб одержати апроксимацію добутку Xa·Fa. Масштабований множник перетворення Fa/C /4 може бути апроксимований за допомогою раціональної двійкової константи βa, яка може бути помножена на Хb, щоб одержати апроксимацію добутку Xb·Fa/C /4. Змінені масштабні множники А2/Fa і A6/Fa 92780 14 можуть бути застосовані до коефіцієнтів перетворення Х[2] і Х[6], відповідно. Другий загальний множник Fb може бути апроксимований за допомогою раціональної двійкової константи αb, яка може бути помножена на Xd, щоб одержати апроксимацію добутку Xd·Fb. Масштабований множник перетворення Fb/C /4 може бути апроксимований за допомогою раціональної двійкової константи βb, яка може бути помножена на Хс, щоб одержати апроксимацію добутку Xc·Fb/C /4. Масштабований множник перетворення 2Fb·C3 /8 може бути апроксимований за допомогою раціональної двійкової константи b, a масштабований множник перетворення 2Fb·S3 /8 може бути апроксимований за допомогою раціональної двійкової константи b. Раціональна двійкова константа b, може бути помножена на Хе, щоб одержати апроксимацію добутку 2Xe·Fb·C3 /8, a також на Xf, щоб одержати апроксимацію добутку 2Xf·Fb·C3 /8. Раціональна двійкова константа b, може бути помножена на Хс, щоб одержати апроксимацію добутку 2Xc·Fb·S3 /8, а також на Xf, щоб одержати апроксимацію добутку 2Xf·Fb·S3 /8. Змінені масштабні множники A1/Fb, A3/Fb, A5/Fb і A7/Fb можуть бути застосовані до коефіцієнтів перетворення Х[1], Х[3], Х[5] і Х[7], відповідно. Шість раціональних двійкових констант αa, βa, αb, βb, b і b можуть бути визначені для шести констант таким чином: αa Fa, βa Fa·cos( /4), αb Fb, βb Fb·cos( /4), b 2Fb·cos(3 /8) i Рівняння (4) b 2Fb·sin(3 /8). Фіг.3 і Фіг.4 зображають типове використання загальних множників для конкретних факторизацій 8-ми точкового IDСТ і 8-ми точкового DCT, відповідно. Загальні множники можуть бути використані для інших факторизацій DCT і IDCT, а також для інших типів перетворень. Звичайно загальний множник може бути застосований до групи щонайменше з однієї проміжної змінної в перетворенні. Ця група проміжної змінної (змінних) може бути згенерована з групи вхідних величин (наприклад, як зображено на Фіг.3) або використана, щоб згенерувати групу вихідних величин (наприклад, як зображено на Фіг.4). Загальний множник може бути обчислений за допомогою масштабних множників, застосованих до вхідних величин або вихідних величин. Множина загальних множників може бути застосована до множини груп проміжних змінних, і кожна група може включати в себе будь-яке число проміжних змінних. Вибір груп може залежати від різних факторів, таких як факторизація перетворення, де константи перетворення знаходяться в перетворенні і т.д. Множина загальних множників може бути застосована до множини груп проміжних змінних одного і того ж розміру (не зображено на Фіг.3 і Фіг.4) або різних розмірів (як зображено на Фіг.3 і Фіг.4). Наприклад, три загальних множники можуть бути використані для факторизації, зображеної на Фіг.3, причому перший загальний множник застосований до проміжних змінних X1 і Х2, другий загальний множник застосований до проміжних змінних Х3, Х4, X5 і Х6, а третій проміж 15 ний множник застосований до двох проміжних змінних, згенерованих з Х[0] і Х[4]. Множення проміжної змінної x на раціональну двійкову константу u може бути виконане різними способами в цілочисловій арифметиці з фіксованою точкою. Множення може бути виконане з використанням логічних операцій (наприклад, зсув ліворуч, зсув праворуч, інверсія бітів і т.д.), арифметичних операцій (наприклад, додавання, віднімання, інверсія знака і т.д.) і/або інших операцій. Число логічних і арифметичних операцій, необхідних для множення x на u, залежить від способу, яким виконують обчислення, і величини раціональної двійкової константи и. Різні способи обчислення можуть потребувати різного числа логічних і арифметичних операцій для одного і того ж множення x на u. Даний спосіб обчислення може потребувати різного числа логічних і арифметичних операцій для множення x на різні величини u. Загальний множник може бути вибраний для групи проміжних змінних на основі критеріїв, таких як: число логічних і арифметичних операцій, щоб виконати множення, і точність результатів. Звичайно бажано мінімізувати число логічних і арифметичних операцій, необхідних для множення проміжної змінної на раціональну двійкову константу. У деяких платформах апаратного забезпечення арифметичні операції (наприклад, додавання) можуть бути більш складними, ніж логічні операції, таким чином, зменшення числа арифметичних операцій може бути більш важливим. У граничному випадку обчислювальна складність може бути кількісно оцінена на основі тільки числа арифметичних операцій, без урахування логічних операцій. У деяких інших платформах апаратного забезпечення логічні операції (наприклад, зсуви) можуть бути більш дорогими, і зменшення числа логічних операцій (наприклад, зменшення числа операцій зсуву і/або повного числа зсунутих бітів) може бути більш важливим. Звичайно може бути використане зважене середнє число логічних і арифметичних операцій, де ваги можуть представляти відносні складності логічних і арифметичних операцій. Точність результатів кількісно може бути оцінена на основі різних показників, таких як показники, наведені в таблиці 6 нижче. Звичайно бажано зменшити число логічних і арифметичних операцій (або обчислювальної складності) для даної точності. Також може бути бажаним приймати компромісне рішення на користь складності заради точності, наприклад, щоб досягнути більш високої точності за рахунок деяких додаткових операцій. Як зображено на Фіг.3 і Фіг.4, для кожного загального множника множення може бути виконане відносно групи проміжних змінних на групу раціональних двійкових констант, яка апроксимує групу щонайменше з однієї ірраціональної константи (щонайменше для одного коефіцієнта перетворення), масштабованої за допомогою цього загального множника. Множення в цілочисловій арифметиці з фіксованою точкою може бути виконане різними способами. Для пояснення способи обчи 92780 16 слення, які виконують множення за допомогою операцій зсуву і додавання і з використанням проміжних результатів, описані нижче. Ці способи обчислення можуть зменшити загальне число операцій зсуву і додавання для DCT і IDCT. Множення цілої змінної x на ірраціональну константу в цілочисловій арифметиці з фіксованою точкою може бути виконане за допомогою апроксимації ірраціональної константи за допомогою раціональної двійкової константи таким чином: Рівняння (5) c/2b де - апроксимована ірраціональна константа, с/2b - раціональна двійкова константа, b і с цілі, і b>0. Якщо дана ціла змінна x і раціональна двійкова константа u=c/2b, цілочисловий добуток у=(х·с)/2b Рівняння (6) може бути апроксимоване з використанням послідовності проміжних величин y0, y1, y2, …, yt Рівняння (7) де у0=0, у1=х, і для всіх величин 2 i t величини yt одержують таким чином: Si уt=±yj±уk·2 , при j,k0 і d>0. Якщо задані ціла змінна x і раціональні двійкові константи u=c/2b і e/2d, два цілочислових добутки y=(x·с)/2b і z=(х·е)/2d Рівняння (11) 17 можуть бути апроксимовані з використанням послідовності проміжних величин w0, w1, w2, …, wt Рівняння (12) де W0=0, w1=x і для всіх величин 2 i t wi одержують таким чином: wi=±wj±wk·2Si , при j,k>2), //101 Рівняння (19) у3=у1-(у2>>2) //01011 у4=у3+(у2>>6), //010110101 Двійкова величина праворуч від "//" є проміжною константою, яку множать на змінну х. Бажаний добуток дорівнює у4 або у4=у. Множення в рівнянні (18) може бути виконане за допо 92780 18 могою трьох додавань і трьох зсувів, щоб згенерувати три проміжні величини у2, у3 і у4. На Фіг.1 множення цілої змінної χ на константи перетворення С3 /8 і S3 /8 в цілочисловій арифметиці з фіксованою точкою може бути виконане за допомогою апроксимації констант С3 /8 і S3 /8 раціональними двійковим константами таким 49 b00110001 Рівняння (20) С7 3 / 8 128 b10000000 473 b0111011001 Рівняння (21) S9 / 8 3 512 b1000000000 де С7 - раціональна двійкова константа, 3 /8 яка є 7-ми бітовою апроксимацією С3 /8, a - раціональна двійкова константа, яка S9 3 /8 є 9-ти бітовою апроксимацією S3 /8. Множення цілої змінної x на константи С7 3 /8 9 і S3 / 8 може бути виражене таким чином: У=(х·49)/128 і z=(x·473)/512 Рівняння (22) Множення в рівнянні (22) можуть бути виконані за допомогою наступної послідовності операцій: w1=х, //1 w2=w1-(w1>>2), //11 w3=w1>>6, //0000001 w4=w2+w3, //0110001 Рівняння (23) w5=w1-w3, //0111111 w6=w4>>1, //00110001 w7=w5-(w1>>4), //0111011 w8=w7+(w1>>9), //0111011001 Бажані добутки дорівнюють w6 і w8 або w6=y і w8=z. Два множення в рівнянні (22) можуть бути спільно виконані за допомогою п'яти додавань і п'яти зсувів, щоб згенерувати сім проміжних величин з w2 no w8. Додавання нулів пропущені при генерації w3 і w6. Зсуви на нуль пропущені при генерації w4 і w5. Для 8-ми точкового IDСТ, зображеного на Фіг.1, з використанням способів обчислення, описаних вище для множень на константи С8 , /4 , S9 , повна складність для 8-ми бітової С7 3 /8 3 /8 точності може бути одержана як: 28+3·2+5·2=44 додавань і 3·2+5·2=16 зсувів. Звичайно будь-яка бажана точність може бути досягнута за допомогою використання достатнього числа бітів для апроксимації кожної константи перетворення. Для 8-ми точкового DCT, зображеного на Фіг.2, ірраціональні константи 1/C /4, С3 /8 і S3 /8 можуть бути апроксимовані раціональними двійковими константами. Множення на раціональні двійкові константи можуть бути виконані з використанням способів обчислень, описаних вище. Для IDСТ, зображеного на Фіг.3, різні величини загальних множників F1 і F2 можуть давати в результаті різні повні числа логічних і арифметичних операцій для IDCT і різні рівні точності для вихідних вибірок з х[0] по х[7]. Можуть бути оцінені різні комбінації величин F1 і F2. Для кожної комбінації величин може бути визначене повне число логіч 19 них і арифметичних операцій для IDCT і точність вихідних вибірок. Для даної величини F1 раціональні двійкові константи α1 і β1 можуть бути одержані для F1 і F1·C /4, відповідно. Числа логічних і арифметичних операцій тоді можуть бути визначені для множення Х1 на α1 і множення Х2 на β1. Для даної величини F2 раціональні двійкові константи α2, β2, 2 і 2 можуть бути одержані для F2, F2 C /4, F2 C3 /8 і F2 S3 /8 відповідно. Числа логічних і арифметичних операцій тоді можуть бути визначені для множення Х4 на α2, множення Х3 на β2 і множення Х5, як на 2, так і на 2. Число операцій, необхідних для множення Х6 на 2 і 2, дорівнює числу операцій, необхідних для множення Х5 на 2 і 2. Щоб полегшити оцінку і вибір загальних множників, число логічних і арифметичних операцій може бути попередньо обчислене для множення на різні можливі величини раціональних двійкових констант. Попередньо обчислене число логічних і арифметичних операцій може бути збережене в довідковій таблиці або в деякій іншій структурі даних. Фіг.5 зображує довідкову таблицю 500, яка зберігає числа логічних і арифметичних операцій, необхідних для множення на різні величини раціональних двійкових констант. Довідкова таблиця 500 є двовимірною таблицею з різними можливими величинами першої раціональної двійкової константи С1 по горизонтальній осі і різними можливими величинами другої раціональної двійкової константи С2 по вертикальній осі. Число можливих величин для кожної раціональної двійкової константи залежить від числа бітів, використаних для константи. Наприклад, якщо С1 представлена за допомогою 13 бітів, тоді є 8192 можливі величини для С1. Можливі величини для кожної раціональної двійкової константи позначені як с0, с1, с2, ..., сМ, де c0=0, с1 - найменша ненульова величина, а сM - максимальна величина (наприклад, сM=8191 для 13 бітів). Елемент в і-тому стовпці і j-тому рядку довідкової таблиці 500 містить число логічних і арифметичних операцій, необхідних для об'єднаного множення проміжної змінної х, як на ci для першої раціональної двійкової константи С1, так і на C1 для другої раціональної двійкової константи С2. Величина для кожного елемента в довідковій таблиці 500 може бути визначена за допомогою оцінки різних можливих послідовностей проміжних величин для об'єднаного множення на ci і cj для цього елемента і вибору найкращої послідовності, наприклад послідовності з найменшим числом операцій. Елементи в першому рядку довідкової таблиці 500 (з c0=0 для другої раціональної двійкової константи С2) містять числа операцій, необхідних для множення проміжної змінної x тільки на с1 для першої раціональної двійкової константи С1. Оскільки довідкова таблиця є симетричною, можуть бути заповнені елементи тільки в половині таблиці (наприклад, вище або нижче головної діагоналі). Крім того, число елементів для заповнення може бути зменшене, якщо взяті до уваги ірраціо 92780 20 нальні константи, апроксимовані за допомогою раціональних двійкових констант С1 і С2. Для даної величини F1 можуть бути визначені раціональні двійкові константи α1 і β1. Число логічних і арифметичних операцій, необхідних для множення Х1 на α1 і множення Х2 на β1, може бути легко визначено з елементів в першому рядку довідкової таблиці 500, де α1 і β1 відповідають С1. Подібним чином для даної величини F2 можуть бути визначені раціональні двійкові константи α2, β2, 2 і 2. Число логічних і арифметичних операцій, необхідних для множення Х4 на α2 і множення Х3 на β2, може бути визначено з елементів в першому рядку довідкової таблиці 500, де α2 і β2 відповідають С1. Число логічних і арифметичних операцій, необхідних для об'єднаного множення Х5 на 2 і 2, може бути визначено з відповідного елемента в довідковій таблиці 500, де 2 може відповідати С1, а 2 може відповідати С2, або навпаки. Для кожної можливої комбінації величин F1 і F2 показники якості в таблиці 6 можуть бути визначені для достатнього числа ітерацій з різними випадковими вхідними даними. Величини F1 і F2, які дають в результаті низьку точність (наприклад, невиконання показників), можуть бути відкинуті, а величини F1 і F2, які дають в результаті хорошу точність (наприклад, прохід показників), можуть бути збережені. Таблиці з 1 по 5 зображають п'ять апроксимацій з фіксованою точкою для IDCT на Фіг.3, які позначені як алгоритми А, В, С, D і Е. Ці апроксимації представлені для двох груп множників, причому одна група включає в себе α1 і β1, а інша група включає в себе α2, β2, 2 і 2. Для кожної з таблиць з 1 по 5 загальний множник для кожної групи наведений в першому стовпці. Загальні множники підвищують точність апроксимацій раціональною двійковою константою і можуть бути об'єднані з відповідними масштабними множниками в графсхемі для IDCT. Вихідні величини (які можуть бути 1 або ірраціональними константами) наведені в третьому стовпці. Раціональна двійкова константа для кожної вихідної величини, масштабованої за допомогою її загального множника, наведена в четвертому стовпці. Послідовність проміжних величин для множення проміжної змінної x на одну або дві раціональні двійкові константи наведена в п'ятому стовпці. Числа операцій додавання і зсуву для кожного множення наведені в шостому і сьомому стовпцях, відповідно. Повне число операцій додавання для IDСТ дорівнює сумі всіх операцій додавання в шостому стовпці плюс останній елемент знову (щоб обчислити множення для кожного з Х5 і Х6, як на 2, так і на 2), плюс 28 операцій додавання для всіх операцій метелика в графсхемі. Повне число операцій зсуву для IDСТ дорівнює сумі всіх операцій зсуву в останньому стовпці плюс знову останній елемент. Таблиця 1 дає деталі алгоритму А, який використовує загальний множник, рівний 1/1,0000442471, для кожної з двох груп. 21 92780 22 Таблиця 2 дає деталі алгоритму В, який використовує загальний множник, рівний 1/1,0000442471, для першої групи, і загальний множник, рівний 1/1,02053722659, для другої групи. Таблиця 3 дає деталі алгоритму С, який використовує загальний множник, рівний 1/0,87734890555, для першої групи, і загальний множник, рівний 1/1,02053722659, для другої групи. 23 92780 24 Таблиця 4 дає деталі алгоритму D, який використовує загальний множник, рівний 1/0,87734890555, для першої групи, і загальний множник, рівний 1/0,89062054308, для другої групи. Таблиця 5 дає деталі алгоритму Е, який використовує загальний множник, рівний 1/0,87734890555, для першої групи, і загальний множник, рівний 1/1,22387468002, для другої групи. 25 92780 26 Точність вихідних вибірок з апроксимуючого IDCT може бути кількісно оцінена на основі показників, визначених в стандарті 1180-1190 IEEE, і в його замінах, що розглядаються. Цей стандарт визначає тестування еталонного 64-бітового DCT з плаваючою точкою, за яким іде апроксимуюче IDCT з використанням даних з генератора випадкових чисел. Еталонне DCT приймає випадкові дані для блока вхідних пікселів і генерує коефіцієнти перетворення. Апроксимуюче IDСТ приймає коефіцієнти перетворення (округлені відповідним чином) і генерує блок відновлених пікселів. Відновлені піксели порівнюють з вхідними пікселами з використанням п'яти показників, які наведені в таблиці 6. Крім того, потрібно, щоб апроксимуюче IDCT видавало всі нулі при подачі нульових коефіцієнтів перетворення і демонструвало поведінку майже постійного зворотного перетворення. Всі п'ять алгоритмів з А по Е, наведені вище, проходять всі показники в таблиці 6. 1D IDCT, зображене на Фіг.3, може бути використане для 2D IDCT. Подібним чином 1D IDCT, зображене на Фіг.4, може бути використане для 2D IDCT. Фіг.6 зображує конструкцію 2D IDCT 600, здійснену масштабованим і розділюваним способом. 2D IDCT 600 містить вхідний каскад 612 масштабування, за яким іде перший каскад 614 масшта 27 бованого 1D IDCT для стовпців (або рядків), за яким додатково іде другий каскад 616 масштабованого 1D IDСТ для рядків (або стовпців) і закінчуючи вихідним каскадом 618 масштабування. Вхідний каскад 612 масштабування приймає блок 8×8 коефіцієнтів перетворення і може попередньо помножити кожний коефіцієнт перетворення на константу С=2Р або зсунути кожний коефіцієнт перетворення на Ρ бітів ліворуч, де Ρ означає число зарезервованих бітів "мантиси". Після масштабування величина 2P-1 може бути додана до постійного коефіцієнта перетворення, щоб одержати відповідне округлення у вихідних вибірках. Щоб збільшити точність масштабування, S=P+R бітів можуть бути використані в перетворенні масштабних множників в цілі, і зсуви праворуч на R бітів можуть бути виконані після множення. S може бути будь-якою придатною величиною, яка може полегшити здійснення на платформах апаратного забезпечення, наприклад, S може бути 15 або 16 для платформ з 16-ти бітовими помножувачами зі знаком/без знака. Перший каскад 614 1D IDСТ виконує 8-ми точкове IDСТ відносно кожного стовпця блока масштабованих коефіцієнтів перетворення. Другий каскад 616 1D IDCT виконує 8-ми точкове IDCT відносно кожного рядка проміжного блока, згенерованого за допомогою першого каскаду 614 1D IDCT. 1D IDСТ для першого і другого каскадів можуть оперувати безпосередньо відносно їх вхідних даних без виконання якого-небудь внутрішнього попереднього або подальшого масштабування. Після того, як рядки і стовпці оброблені, вихідний каскад 618 масштабування може зсунути результуючі величини з другого каскаду 616 1D IDCT на Ρ бітів праворуч, щоб згенерувати вихідні вибірки для 2D IDСТ. Масштабні множники і константа Ρ точності можуть бути вибрані таким чином, що все 2D IDСТ може бути здійснене з використанням регістрів бажаної довжини. 2D DCT може бути виконане подібним чином, що і 2D IDСТ. 2D IDСТ може бути виконане за допомогою (а) попереднього множення блока вибірок просторової області визначення, (b) виконання 1D IDСТ відносно кожного стовпця (або рядка) блока масштабованих вибірок, щоб згенерувати проміжний блок, (с) виконання 1D IDСТ відносно кожного рядка (або стовпця) проміжного блока і (d) масштабування вихідних даних другого каскаду 1D IDСТ, щоб згенерувати блок коефіцієнтів перетворення для 2D IDCT. Для пояснення більша частина опису вище призначена для 8-ми точкового масштабованого IDСТ і 8-ми точкового масштабованого DCT. Способи, описані в даній заявці, можуть бути використані для будь-якого типу перетворення, такого як DCT, IDCT, DFT, IDFT, MLT, зворотне MLT, MCLT, зворотне MCLT і т.д. Способи також можуть бути використані для будь-якої факторизації перетворення, причому декілька типових факторизацій наведені на Фіг.1 по Фіг.4. Групи для загальних множників можуть бути вибрані на основі факторизації, як описано вище. Способи також можуть бути використані для перетворень будь-якого розміру, причому типові 8-ми точкові перетворення 92780 28 наведені на Фіг.1 по Фіг.4. Способи також можуть бути використані в поєднанні з будь-яким критерієм вибору загального множника, таким як повне число логічних і арифметичних операцій, повне число арифметичних операцій, точність результатів і т.д. Число операцій для перетворення може залежати від способу, яким виконують множення. Способи обчислення, описані вище, розгортають множення в послідовність операцій зсуву і додавання, використовують проміжні результати, щоб зменшити число операцій, і виконують об'єднане множення на множину констант з використанням загальної послідовності. Множення також можуть бути виконані за допомогою інших способів обчислення, які можуть впливати на вибір загальних множників. Перетворення із загальними множниками, описані в даній заявці, можуть забезпечувати певні переваги, такі як: менша складність множення внаслідок об'єднаних множень на масштабованому етапі, можливе зменшення складності внаслідок можливості об'єднувати масштабування з квантуванням в реалізаціях JPEG, H.263, MPEG-1, MPEG-2, MPEG-4 (P.2) і інших стандартів, і збільшена точність внаслідок можливості мінімізувати/розподілити похибки апроксимацій з фіксованою точкою для ірраціональних констант, використовуваних в множенні, за допомогою введення загальних множників, які можуть бути обчислені за допомогою масштабних множників. Перетворення із загальними множниками можуть бути використані для різних застосувань, таких як обробка зображення і відео, обмін даними, обчислення, передача даних по мережі, зберігання даних, графіка і т.д. Типове використання перетворень для обробки відео описане нижче. Фіг.7 зображує блок-схему системи 700 кодування і декодування зображення/відео. У системі 710 кодування пристрій 720 DCT приймає блок вхідних даних і генерує блок коефіцієнтів перетворення. Блок вхідних даних може бути блоком Ν×Ν пікселів, блоком Ν×Ν величин різниці пікселів (або залишку) або деякого іншого типу даних, згенерованих з вихідного сигналу, наприклад, відеосигналу. Величини різниці пікселів можуть бути різницями між двома блоками пікселів, різницями між блоком пікселів і блоком передбачених пікселів і т.д. N може дорівнює 8 або деякій іншій величині. Кодер 730 приймає блок коефіцієнтів перетворення з вузла 720 DCT, кодує коефіцієнти перетворення і генерує стиснені дані. Стиснені дані можуть бути збережені у вузлі пам'яті і/або послані через канал зв'язку (хмари 740). У системі 750 декодування декодер 760 приймає стиснені дані з вузла пам'яті або каналу 740 зв'язку і відновлює коефіцієнти перетворення. Пристрій 770 IDCT приймає відновлені коефіцієнти перетворення і генерує блок вихідних даних. Блок вихідних даних може бути блоком Ν×Ν відновлених пікселів, блоком Ν×Ν величин різниці відновлених пікселів і т.д. Блок вихідних даних може бути оцінкою блока вхідних даних, наданих у вузлі 720 DCT, і може бути використаний, щоб відновлювати вихідний сигнал. 29 Фіг.8 зображує блок-схему системи 800 кодування, яка може бути використана для системи 710 кодування на Фіг.7. Пристрій захоплення/пам'яті 810 може приймати вихідний сигнал, виконувати конвертацію в цифровий формат і надає вхідні/необроблені дані. Пристрій 810 захоплення може бути відеокамерою, цифратором або деяким іншим пристроєм. Процесор 820 обробляє необроблені дані і генерує стиснені дані. У процесорі 820 необроблені дані можуть бути перетворені за допомогою вузла 822 DCT, скановані за допомогою вузла 824 зигзагоподібного сканування, квантовані за допомогою квантувача 826, закодовані за допомогою кодера 824 з ентропією і пакетовані за допомогою формувача 830 пакетів. Вузол 822 DCT може виконувати 2D DCT відносно необроблених даних відповідно до способів, описаних вище. Кожний з вузлів з 822 по 830 може бути здійснений як апаратне забезпечення, програмно-апаратне забезпечення і/або програмне забезпечення. Наприклад, пристрій 822 DCT може бути здійснений за допомогою спеціалізованого апаратного забезпечення, множини інструкцій для арифметичного логічного пристрою (ALU) і т.д. Вузол 840 зберігання може зберігати стиснені дані з процесора 820. Передавач 842 може передавати стиснені дані. Контролер/процесор 850 керує роботою різних вузлів в системі 800 кодування. Пам'ять 852 зберігає дані і програмні коди для системи 800 кодування. Одна або більше шин 860 взаємно з'єднують різні вузли в системі 800 кодування. Фіг.9 зображує блок-схему системи 900 декодування, яка може бути використана для системи 750 декодування на Фіг.7. Приймач 910 може приймати стиснені дані з системи кодування, а вузол 912 зберігання може зберігати прийняті стиснені дані. Процесор 920 обробляє стиснені дані і генерує вихідні дані. У процесорі 920 стиснені дані можуть бути розпаковані за допомогою розпаковувача 922, декодовані за допомогою декодера 924 з ентропією, зворотно квантовані за допомогою зворотного квантувача 924, розташовані у відповідному порядку за допомогою вузла 928 зворотного зигзагоподібного сканування і перетворені за допомогою вузла 930 IDCT. Вузол 930 IDCT може виконувати 2D IDСТ відносно відновлених коефіцієнтів перетворення відповідно до способів, описаних вище. Кожний з вузлів з 922 по 930 може бути здійснений як апаратне забезпечення, програмноапаратне забезпечення і/або програмне забезпечення. Наприклад, вузол 930 IDСТ може бути здійснений за допомогою спеціалізованого апаратного забезпечення, набору інструкцій для арифметичного логічного пристрою (ALU) і т.д. Вузол 940 відображення відображає відновлені зображення і відео з процесора 920. Контролер/процесор 950 керує роботою різних вузлів в системі 900 декодування. Пам'ять 952 зберігає дані і програмні коди для системи 900 декодування. Одна або більше шин 960 взаємно з'єднують різні вузли в системі 900 декодування. Кожний з процесорів 820 і 920 може бути здійснений за допомогою однієї або більше інтегральних схем прикладної орієнтації (ASIC), процесорів 92780 30 цифрових сигналів (DSP) і/або деякого іншого типу процесорів. Як альтернатива, кожний з процесорів 820 і 920 може бути замінений одним або більше оперативними запам'ятовуючими пристроями (RAM), постійними запам'ятовуючими пристроями (ROM), електрично програмованими ROM (EPROM), електрично стираними перепрограмованими ROM (EEPROM), магнітними дисками, оптичними дисками і/або іншими типами енергозалежних і енергонезалежних пам'ятей, відомими в даній галузі техніки. Способи, описані в даній заявці, можуть бути здійснені в апаратному забезпеченні, програмноапаратному забезпеченні, програмному забезпеченні або їх комбінації. Наприклад, логічні (наприклад, зсув) і арифметичні (наприклад, додавання) операції, необхідні для множення величини даних на постійну величину, можуть бути здійснені за допомогою однієї або більше логік, які також можуть бути згадані як вузли, модулі і т.д. Логіка може бути апаратною логікою, що містить логічні вентилі, транзистори і/або інші схеми, відомі в даній галузі техніки. Логіка також може бути програмноапаратною і/або програмною логікою, що містить машиночитані коди. У одній конструкції пристрій містить першу логіку, щоб виконувати множення першої групи щонайменше з однієї величини даних на першу групу щонайменше з однієї раціональної двійкової константи, яка апроксимує першу групу щонайменше з однієї ірраціональної константи, масштабованої за допомогою першого загального множника. Пристрій додатково містить другу логіку, щоб виконувати множення другої групи щонайменше з однієї величини даних на другу групу щонайменше з однієї раціональної двійкової константи, яка апроксимує другу групу щонайменше з однієї ірраціональної константи, масштабованої за допомогою другого загального множника. Перша і друга групи щонайменше з однієї величини даних мають різні розміри. Перша і друга логіки можуть бути окремими логіками, однією і тією ж загальною логікою або спільною логікою. Для варіанта здійснення за допомогою програмно-апаратного і/або програмного забезпечення множення величини даних на постійну величину може бути виконане за допомогою машиночитаних кодів, які виконують бажані логічні і арифметичні операції. Коди можуть бути апаратно реалізованими або збережені в пам'яті (наприклад, пам'яті 852 на Фіг.8 або 952 на Фіг.9) і виконані за допомогою процесора (наприклад, процесора 850 або 950) або деякого іншого вузла апаратного забезпечення. Способи, описані в даній заявці, можуть бути здійснені в різних типах пристроїв. Наприклад, способи можуть бути здійснені в різних типах процесорів, різних типах інтегральних схем, різних типах електронних пристроїв, різних типах електронних схем і т.д. Фахівцям в даній галузі техніки буде зрозуміло, що інформація і сигнали можуть бути представлені з використанням будь-чого з множини різних технологій і способів. Наприклад, дані, інструкції, команди, інформація, сигнали, біти, символи і 31 елементарні посилки, які можуть згадуватися у всьому вищенаведеному описі, можуть бути представлені напругами, струмами, електромагнітними хвилями, магнітними полями або частинками, оптичними полями або частинками або будь-якою їх комбінацією. Фахівцям в даній галузі техніки додатково зрозуміло, що різні ілюстративні логічні блоки, модулі, схеми і етапи алгоритмів, описані в зв'язку з розкриттям, можуть бути здійснені у вигляді електронного апаратного забезпечення, комп'ютерного програмного забезпечення або комбінації того і іншого. Для того, щоб зрозуміло проілюструвати цю взаємозамінність апаратного забезпечення і програмного забезпечення, різні ілюстративні компоненти, блоки, модулі, схеми і етапи описані вище загалом в поняттях їх функціонального призначення. Здійснюється таке функціональне призначення апаратно або програмно, залежить від конкретного застосування і конструктивних обмежень, накладених на всю систему. Досвідчені практики можуть здійснити описане функціональне призначення різними способами для кожного конкретного додатка, але рішення такого здійснення не повинні інтерпретуватися як такі, що викликають вихід за рамки даного розкриття. Різні ілюстративні логічні блоки, модулі і схеми, описані в зв'язку з розкриттям, можуть бути здійснені або виконані за допомогою процесора загального призначення, DSP, ASIC, вентильної матриці, програмованої в умовах експлуатації (FPGA), або іншого програмованого логічного пристрою, дискретного вентиля або транзисторної логіки, дискретних компонентів апаратного забезпечення або будь-якої їх комбінації, призначеної для виконання функцій, описаних в даній заявці. Процесор загального призначення може бути мікропроцесором, але в альтернативі процесор може бути будь-яким традиційним процесором, контролером, мікроконтролером або кінцевим автоматом. Процесор також може бути здійснений як комбінація обчислювальних пристроїв, наприклад, комбінація DSP і мікропроцесора, множина мікропроцесорів, один або більше мікропроцесорів спільно з ядром DSP або будь-яка інша така конфігурація. У одному або більше типових варіантах здійснення описані функції можуть бути здійснені в апаратному забезпеченні, програмному забезпеченні, програмно-апаратному забезпеченні або в їх комбінації. Якщо здійснені в програмному забезпеченні, функції можуть бути збережені або пере 92780 32 дані як одна або більше інструкцій або код на машиночитаному носії. Машиночитане середовище включає в себе, як середовище зберігання, так і середовище обміну інформацією, включаючи будь-який носій, який полегшує передачу комп'ютерної програми з одного місця в інше. Середовище зберігання може бути будь-яким наявним середовищем, доступ до якого може бути здійснений за допомогою комп'ютера. Як приклад, а не обмеження, таке машиночитане середовище може містити RAM, ROM, EEPROM, CD-ROM або інше сховище на оптичному диску, сховище на магнітному диску або інші пристрої магнітного зберігання, або будь-який інший носій, який може бути використаний для перенесення або зберігання бажаного програмного коду у вигляді інструкцій або структур даних, і доступ до якого може бути здійснений за допомогою комп'ютера. Також будь-яке з'єднання по суті називають машиночитаним носієм. Наприклад, якщо програмне забезпечення передають з web-сайта, сервера або іншого віддаленого джерела з використанням коаксіального кабелю, волоконно-оптичного кабелю, витої пари, цифрової абонентської лінії (DSL) або безпровідних технологій, таких як інфрачервоне випромінювання, радіохвилі і мікрохвилі, тоді коаксіальний кабель, волоконно-оптичний кабель, вита пару, DSL або безпровідні технології, такі як інфрачервоне випромінювання, радіохвилі і мікрохвилі, включають у визначення носія. Поняття disk або disc, як використовується в даному описі, включають в себе кохмпакт-диск (CD), лазерний диск, оптичний диск, цифровий універсальний диск (DVD), гнучкий диск, диск blu-ray, де disks звичайно відтворюють дані магнітним способом, в той час як discs відтворюють дані оптичним способом за допомогою лазерів. Комбінації вищепереліченого також потрібно включити в рамки машиночитаного середовища. Попередній опис розкриття наданий для того, щоб дати можливість будь-якому фахівцеві в даній галузі техніки виготовити або використати даний винахід. Різні модифікації розкриття можуть бути без великих зусиль зрозумілі фахівцям в даній галузі техніки, а основні принципи, визначені в даній заявці, можуть бути застосовані до інших конструкцій, не виходячи за рамки суті і об'єму винаходу. Отже, не передбачається, що дане розкриття обмежене прикладами, зображеними в цій заявці, але має відповідати самим широким рамкам, що узгоджуються з принципами і новими ознаками, розкритими в даній заявці. 33 92780 34 35 92780 36 37 92780 38 39 Комп’ютерна верстка Т. Чепелева 92780 Підписне 40 Тираж 26 прим. Міністерство освіти і науки України Державний департамент інтелектуальної власності, вул. Урицького, 45, м. Київ, МСП, 03680, Україна ДП “Український інститут промислової власності”, вул. Глазунова, 1, м. Київ – 42, 01601