RU2009102250A - Уменьшение ошибок во время вычисления обратного дискретного косинусного преобразования - Google Patents
Уменьшение ошибок во время вычисления обратного дискретного косинусного преобразования Download PDFInfo
- Publication number
- RU2009102250A RU2009102250A RU2009102250/08A RU2009102250A RU2009102250A RU 2009102250 A RU2009102250 A RU 2009102250A RU 2009102250/08 A RU2009102250/08 A RU 2009102250/08A RU 2009102250 A RU2009102250 A RU 2009102250A RU 2009102250 A RU2009102250 A RU 2009102250A
- Authority
- RU
- Russia
- Prior art keywords
- coefficients
- matrix
- value
- butterfly structure
- operations
- Prior art date
Links
- 230000009466 transformation Effects 0.000 title claims abstract 15
- 238000000034 method Methods 0.000 claims abstract 23
- 230000003287 optical effect Effects 0.000 claims abstract 5
- 239000011159 matrix material Substances 0.000 claims 83
- 238000006243 chemical reaction Methods 0.000 claims 7
- 230000015572 biosynthetic process Effects 0.000 claims 3
Landscapes
- Complex Calculations (AREA)
Abstract
1. Способ, содержащий ! использование последовательности операций структуры бабочки над числами с фиксированной запятой для применения преобразования к вектору исходных коэффициентов для формирования вектора преобразованных коэффициентов, ! причем преобразованные коэффициенты в векторе преобразованных коэффициентов являются аппроксимациями значений, которые формируются преобразованием вектора исходных коэффициентов с использованием идеального обратного дискретного косинусного преобразования, и ! вызов вывода звуковых или оптических сигналов блоком воспроизведения мультимедиа на основе преобразованных коэффициентов в векторе преобразованных коэффициентов, ! причем разности между результатами, сформированными одной из операций структуры бабочки, и результатами, которые формируются эквивалентной операцией структуры бабочки с использованием арифметических операций с неограниченной точностью, сосредоточены вокруг нуля, и положительные разности, и отрицательные разности имеют приблизительно равную величину. ! 2. Способ по п.1, в котором использование последовательности операций структуры бабочки содержит выполнение операции структуры бабочки вида ! u=((x*C)>>k)-((y*-S)>>k'); ! v=((x*S)>>k')-((y*C)>>k), ! где u и v - получающиеся в результате числа с фиксированной запятой, ! где C, S, k и k' - постоянные целые числа, ! где x и y - переменные с фиксированной запятой, и ! где C/2k и S/2k - аппроксимации рациональным числом иррациональных констант. ! 3. Способ по п.2, ! в котором вектор исходных коэффициентов состоит из восьми коэффициентов: x0, x1, x2, x3, x4, x5, x6 и x7, ! в котором вектор преобразованных коэффициентов состоит из восьми коэффицие
Claims (61)
1. Способ, содержащий
использование последовательности операций структуры бабочки над числами с фиксированной запятой для применения преобразования к вектору исходных коэффициентов для формирования вектора преобразованных коэффициентов,
причем преобразованные коэффициенты в векторе преобразованных коэффициентов являются аппроксимациями значений, которые формируются преобразованием вектора исходных коэффициентов с использованием идеального обратного дискретного косинусного преобразования, и
вызов вывода звуковых или оптических сигналов блоком воспроизведения мультимедиа на основе преобразованных коэффициентов в векторе преобразованных коэффициентов,
причем разности между результатами, сформированными одной из операций структуры бабочки, и результатами, которые формируются эквивалентной операцией структуры бабочки с использованием арифметических операций с неограниченной точностью, сосредоточены вокруг нуля, и положительные разности, и отрицательные разности имеют приблизительно равную величину.
2. Способ по п.1, в котором использование последовательности операций структуры бабочки содержит выполнение операции структуры бабочки вида
u=((x*C)>>k)-((y*-S)>>k');
v=((x*S)>>k')-((y*C)>>k),
где u и v - получающиеся в результате числа с фиксированной запятой,
где C, S, k и k' - постоянные целые числа,
где x и y - переменные с фиксированной запятой, и
где C/2k и S/2k - аппроксимации рациональным числом иррациональных констант.
3. Способ по п.2,
в котором вектор исходных коэффициентов состоит из восьми коэффициентов: x0, x1, x2, x3, x4, x5, x6 и x7,
в котором вектор преобразованных коэффициентов состоит из восьми коэффициентов: z0, z1, z2, z3, z4, z5, z6 и z7, и
выполнение любой из операций структуры бабочки содержит
выполнение первой операции структуры бабочки, в которой x=x0, y=x4, C=1, S=1, u=x0' и v=x4',
выполнение второй операции структуры бабочки, в которой x=x2, y=x6, C=α, S=β, u=x6', v=x2',
выполнение третьей операции структуры бабочки, в которой x=x7, y=x1, C=1, S=1, u=x7' и v=x1',
выполнение четвертой операции структуры бабочки, в которой x=
*x1', y=x5, C=1, S=1, u=x1'' и v=x5',
выполнение пятой операции структуры бабочки, в которой x=*x7', y=x3, C=1, S=1, u=x7'' и v=x3',
выполнение шестой операции структуры бабочки, в которой x=x0', y=x6', C=1, S=1, u=x0'' и v=x6'',
выполнение седьмой операции структуры бабочки, в которой x=x4', y=x2', C=1, S=1, u=x4'' и v=x2'',
выполнение восьмой операции структуры бабочки, в которой x=x1'', y=x7'', C=ζ, S=ε, u= x1''' и v=x7''',
выполнение девятой операции структуры бабочки, в которой x=x3', y=x5', C=δ, S=γ, u=x5'' и v=x3''
выполнение десятой операции структуры бабочки, в которой x=x0'', y=x7''', C=1, S=1, u=z0 и v=z7,
выполнение одиннадцатой операции структуры бабочки, в которой x=x4'', y=x5'', C=1, S=1, u=z1 и v=z6,
выполнение двенадцатой операции структуры бабочки, в которой x=x2'', y=x3'', C=1, S=1, u=z2 и v=z5, и
выполнение тринадцатой операции структуры бабочки, в которой x=x6'', y=x1''', C=1, S=1, u=z3 и v=z4.
4. Способ по п.3, в котором α, β, γ, δ, ε и ζ являются аппроксимациями иррациональных значений 
, 
, и
, соответственно.
5. Способ по п.4, в котором α=8867/16384, β=21407/16384, γ=5681/4096, δ=565/2048, ε=9633/8192, ζ=12873/16384.
6. Способ по п.2, в котором использование последовательности операций структуры бабочки содержит использование последовательности операций сдвига, сложения и вычитания, в результате которых получаются значения, которые аппроксимируют значения, которые получаются в результате выполнения операций умножения в операциях структуры бабочки.
7. Способ по п.1, в котором способ также содержит
формирование матрицы масштабированных коэффициентов посредством масштабирования каждого коэффициента в матрице входных коэффициентов,
формирование матрицы смещенных коэффициентов, которая включает в себя вектор исходных коэффициентов добавлением одного или нескольких значений смещения к коэффициенту DC матрицы масштабированных коэффициентов,
использование последовательности операций структуры бабочки над числами с фиксированной запятой для применения преобразования к каждой вектор-строке в матрице коэффициентов для формирования матрицы промежуточных коэффициентов,
использование последовательности операций структуры бабочки над числами с фиксированной запятой для применения преобразования к каждому вектор-столбцу в матрице промежуточных коэффициентов для формирования матрицы преобразованных коэффициентов, и
формирование матрицы значений компонента пикселя посредством сдвига вправо коэффициентов в матрице преобразованных коэффициентов на первое значение.
8. Способ по п.7,
в котором формирование матрицы смещенных коэффициентов содержит добавление значения смещения центра к коэффициенту DC матрицы масштабированных коэффициентов, и
в котором значение смещения центра равно 2(P+T-1), где P равно первому значению, и T является количеством битов, добавляемых выполнением преобразования.
9. Способ по п.8,
в котором формирование матрицы смещенных коэффициентов содержит добавление значения дополнительного смещения к коэффициенту DC матрицы масштабированных коэффициентов,
в котором добавление значений дополнительного смещения к коэффициенту DC делает положительные ошибки и отрицательные ошибки, в среднем, равными по величине и, в среднем, симметричными относительно нуля, и
в котором ошибки представляют разности между значениями, которые получаются в результате сдвига вправо представлений коэффициентов с фиксированной запятой ограниченной точности в матрице преобразованных коэффициентов на первую величину, и результатами от деления коэффициентов в матрице преобразованных коэффициентов на 2P, где P равно первой величине, без учета точности.
10. Способ по п.9, в котором значение дополнительного смещения равно -1, когда коэффициент DC является отрицательным, и равно 0, когда коэффициент DC является неотрицательным.
11. Способ по п.9,
причем этот способ также содержит, выбор, на псевдослучайной основе, значения, которое равно или -1 или 0, и
в котором добавление значения дополнительного смещения содержит добавление выбранного значения.
12. Способ по п.7,
в котором формирование матрицы масштабированных коэффициентов содержит сдвиг влево каждого коэффициента в матрице входных коэффициентов на второе значение,
в котором использование последовательности операций структуры бабочки для применения преобразования вызывает включение в каждый коэффициент в матрице преобразованных коэффициентов количества дополнительных битов точности, измеряемого третьим значением, и
в котором первое значение равно второму значению плюс третье значение.
13. Способ по п.12, в котором второе значение равно количеству битов мантиссы чисел с фиксированной запятой, используемых при применении преобразования.
14. Способ по п.13,
в котором вторым значением является три, и
в котором, с учетом матрицы входных коэффициентов, значения компонента пикселя удовлетворяют требованиям по точности стандарта 1180 Института инженеров по электротехнике и радиоэлектронике (IEEE).
15. Способ по п.7, причем этот способ также содержит
создание пикселей, которые включают в себя значения компонента пикселя в матрице значений компонента пикселя, и
предписание блоку отображения отображать пиксели.
16. Способ по п.1, в котором числа с фиксированной запятой являются 16-разрядными числами с фиксированной запятой.
17. Устройство, содержащее
модуль обратного преобразования, который использует последовательности операций структуры бабочки над числами с фиксированной запятой для применения преобразования к вектору исходных коэффициентов для формирования вектора преобразованных коэффициентов,
причем преобразованные коэффициенты в векторе преобразованных коэффициентов являются аппроксимациями значений, которые формируются преобразованием вектора исходных коэффициентов с использованием идеального обратного дискретного косинусного преобразования,
в котором блок воспроизведения мультимедиа может воспроизводить звуковые или оптические сигналы на основе преобразованных коэффициентов в векторе преобразованных коэффициентов,
причем разности между результатами, сформированными одной из операций структуры бабочки, и результатами, которые формируются эквивалентной операцией структуры бабочки с использованием арифметических операций с неограниченной точностью, сосредоточены вокруг нуля, и положительные разности и отрицательные разности имеют приблизительно равную величину.
18. Устройство по п.17, в котором одна из операций структуры бабочки, выполненная модулем обратного преобразования, имеет вид
u=((x*C)>>k)-((y*-S)>>k'),
v=((x*S)>>k')-((y*C)>>k),
где u и v - получающиеся в результате значения с фиксированной запятой,
где C, S, k и k' - постоянные целые числа,
где x и y - переменные с фиксированной запятой, и
где C/2k и S/2k - аппроксимации рациональным числом иррациональных констант.
19. Устройство по п.18,
в котором вектор исходных коэффициентов состоит из восьми коэффициентов: x0, x1, x2, x3, x4, x5, x6 и x7,
в котором вектор преобразованных коэффициентов состоит из восьми коэффициентов: z0, z1, z2, z3, z4, z5, z6 и z7, и
в котором модуль обратного преобразования выполняет операции структуры бабочки посредством
выполнения первой операции структуры бабочки, в которой x=x0, y=x4, C=1, S=1, u=x0', v=x4',
выполнение второй операции структуры бабочки, в которой x=x2, y=x6, C=α, S=β, u=x6' и v=x2',
выполнение третьей операции структуры бабочки, в которой x=x7, y=x1, C=1, S=1, u=x7' и v=x1',
выполнение четвертой операции структуры бабочки, в которой x=*x1', y=x5, C=1, S=1, u=x1'' и v=x5',
выполнение пятой операции структуры бабочки, в которой x=*x7', y=x3, C=1, S=1, u=x7'' и v=x3',
выполнение шестой операции структуры бабочки, в которой x=x0', y=x6', C=1, S=1, u=x0'' и v=x6'',
выполнение седьмой операции структуры бабочки, в которой x=x4', y=x2', C=1, S=1, u=x4'' и v=x2'',
выполнение восьмой операции структуры бабочки, в которой x=x1'', y=x7'', C=ζ, S=ε, u= x1''' и v=x7''',
выполнение девятой операции структуры бабочки, в которой x=x3', y=x5', C=δ, S=γ, u=x5'' и v=x3''
выполнение десятой операции структуры бабочки, в которой x=x0'', y=x7''', C=1, S=1, u=z0 и v=z7,
выполнение одиннадцатой операции структуры бабочки, в которой x=x4'', y=x5'', C=1, S=1, u=z1 и v=z6,
выполнение двенадцатой операции структуры бабочки, в которой x=x2'', y=x3'', C=1, S=1, u=z2 и v=z5, и
выполнение тринадцатой операции структуры бабочки, в которой x=x6'', y=x1''', C=1, S=1, u=z3 и v=z4.
20. Устройство по п.19, в котором α, β, γ, δ, ∈ и ζ являются аппроксимациями иррациональных значений , , и, соответственно.
21. Устройство по п.20, в котором α=8867/16384, β=21407/16384, γ=5681/4096, δ=565/2048, ε=9633/8192, ζ=12873/16384.
22. Устройство по п.19, в котором модуль обратного преобразования выполняет операции структуры бабочки с использованием последовательности операций сдвига, сложения и вычитания, в результате которых получаются значения, которые аппроксимируют значения, которые получаются в результате выполнения операций умножения в операциях структуры бабочки.
23. Устройство по п.18, причем это устройство также содержит
модуль масштабирования, который формирует матрицу масштабированных коэффициентов посредством масштабирования каждого коэффициента в матрице входных коэффициентов,
модуль смещения коэффициента, который формирует матрицу смещенных коэффициентов, которая включает в себя вектор исходных коэффициентов добавлением одного или нескольких значений смещения к коэффициенту DC матрицы масштабированных коэффициентов, и
в котором модуль обратного преобразования формирует матрицу промежуточных коэффициентов с использованием последовательности операций структуры бабочки для применения преобразования к каждой вектор-строке в матрице смещенных коэффициентов,
в котором модуль обратного преобразования формирует матрицу преобразованных коэффициентов с использованием последовательности операций структуры бабочки для применения преобразования к каждому вектор-столбцу в матрице промежуточных коэффициентов, и
модуль сдвига вправо, который формирует матрицу значений компонента пикселя посредством сдвига вправо коэффициентов в матрице преобразованных коэффициентов на первое значение,
в котором любой модуль обратного преобразования использует последовательность операций структуры бабочки для применения преобразования к вектору исходных коэффициентов.
24. Устройство по п.23,
в котором модуль смещения коэффициента добавляет значение смещения центра к коэффициенту DC матрицы масштабированных коэффициентов,
причем значение смещения центра равно 2(P+T-1), где P равно первому значению, и T является количеством битов, добавляемых выполнением преобразования.
25. Устройство по п.23,
в котором модуль смещения коэффициента добавляет значение дополнительного смещения к коэффициенту DC матрицы масштабированных коэффициентов,
в котором добавление значения дополнительного смещения к коэффициенту DC делает положительные ошибки и отрицательные ошибки, в среднем, равными по величине и, в среднем, симметричными относительно нуля, и
в котором ошибки представляют разности между значениями, которые получаются в результате сдвига вправо представлений коэффициентов с фиксированной запятой ограниченной точности в матрице преобразованных коэффициентов на первую величину, и результатами от деления коэффициентов в матрице преобразованных коэффициентов на 2P, где P равно первой величине, без учета точности.
26. Устройство по п.25, в котором значение дополнительного смещения равно -1, когда коэффициент DC является отрицательным, и равно 0, когда коэффициент DC является неотрицательным.
27. Устройство по п.25,
в котором модуль смещения коэффициента выбирает, на псевдослучайной основе, значение, которое равно или -1 или 0, и
в котором модуль смещения коэффициента добавляет выбранное значение как значение дополнительного смещения.
28. Устройство по п.23,
в котором модуль масштабирования масштабирует каждый коэффициент в матрице входных коэффициентов посредством сдвига влево каждого коэффициента в матрице входных коэффициентов на второе значение,
в котором модуль обратного преобразования вызывает включение в каждый коэффициент в матрице преобразованных коэффициентов количества дополнительных битов точности, измеряемого третьим значением, и
в котором первое значение равно второму значению плюс третье значение.
29. Устройство по п.28, в котором второе значение равно количеству битов мантиссы чисел с фиксированной запятой, используемых при применении преобразования.
30. Устройство, содержащее
средство для использования последовательности операций структуры бабочки над числами с фиксированной запятой для применения преобразования к вектору исходных коэффициентов для вычисления вектора преобразованных коэффициентов,
причем преобразованные коэффициенты в векторе преобразованных коэффициентов являются аппроксимациями значений, которые формируются преобразованием вектора исходных коэффициентов с использованием идеального обратного дискретного косинусного преобразования,
при этом блок воспроизведения мультимедиа может воспроизводить звуковые или оптические сигналы на основе преобразованных коэффициентов в векторе преобразованных коэффициентов,
причем разности между результатами, сформированными одной из операций структуры бабочки, и результатами, которые формируются эквивалентной операцией структуры бабочки с использованием арифметических операций с неограниченной точностью, сосредоточены вокруг нуля, и положительные разности, и отрицательные разности имеют приблизительно равное значение.
31. Устройство по п.30,
в котором средство для использования последовательности операций структуры бабочки содержит набор средств для выполнения операции структуры бабочки,
причем каждое из средств для выполнения операции структуры бабочки содержит средство для выполнения операции структуры бабочки вида
u=((x*C)>>k)-((y*-S)>>k),
v=((x*S)>>k)-((y*C)>>k),
где u, v, x и y - числа с фиксированной запятой,
где x и y - входные значения, и u и v - выходные значения, и
где C, S и k - целые числа.
32. Устройство по п.31,
в котором вектор исходных коэффициентов состоит из восьми коэффициентов: x0, x1, x2, x3, x4, x5, x6 и x7,
в котором вектор преобразованных коэффициентов состоит из восьми коэффициентов: z0, z1, z2, z3, z4, z5, z6 и z7, и
в котором набор средств для выполнения операций структуры бабочки содержит:
средство для выполнения первой операции структуры бабочки, в которой x=x0, y=x4, C=1, S=1, u=x0' и v=x4',
средство для выполнения второй операции структуры бабочки, в которой x=x2, y=x6, C=α, S=β, u=x6' и v=x2',
средство для выполнения третьей операции структуры бабочки, в который x=x7, y=x1, C=1, S=1, u=x7' и v=x1',
средство для выполнения четвертой операции структуры бабочки, в которой x=*x1', y=x5, C=1, S=1, u=x1'' и v=x5',
средство для выполнения пятой операции структуры бабочки, в которой x=*x7', y=x3, C=1, S=1, u=x7'' и v=x3',
средство для выполнения шестой операции структуры бабочки, в которой x=x0', y=x6', C=1, S=1, u=x0'' и v=x6'',
средство для выполнения седьмой операции структуры бабочки, в которой x=x4', y=x2', C=1, S=1, u=x4'' и v=x2'',
средство для выполнения восьмой операции структуры бабочки, в которой x=x1'', y=x7'', C=ζ, S=ε, u= x1''' и v=x7''',
средство для выполнения девятой операции структуры бабочки, в которой x=x3', y=x5', C=δ, S=γ, u=x5'' и v=x3'',
средство для выполнения десятой операции структуры бабочки, в которой x=x0'', y=x7''', C=1, S=1, u=z0 и v=z7,
средство для выполнения одиннадцатой операции структуры бабочки, в которой x=x4'', y=x5'', C=1, S=1, u=z1 и v=z6,
средство для выполнения двенадцатой операции структуры бабочки, в которой x=x2'', y=x3'', C=1, S=1, u=z2 и v=z5, и
средство для выполнения тринадцатой операции структуры бабочки, в которой x=x6'', y=x1''', C=1, S=1, u=z3 и v=z4.
33. Устройство по п.32, в котором α, β, γ, δ, ε и ζ являются аппроксимациями иррациональных значений , , и, соответственно.
34. Устройство по п.33, в котором α=8867/16384, β=21407/16384, γ=5681/4096, δ=565/2048, ε=9633/8192, ζ=12873/16384.
35. Устройство по п.31, в котором средство для использования последовательности операций структуры бабочки выполняет операции структуры бабочки с использованием последовательности операций сдвига, сложения и вычитания, в результате которых получаются значения, которые аппроксимируют значения, которые получаются в результате выполнения операций умножения в операциях структуры бабочки.
36. Устройство по п.30,
в котором устройство дополнительно содержит
средство для формирования матрицы масштабированных коэффициентов посредством масштабирования каждого коэффициента в матрице входных коэффициентов,
средство для формирования матрицы смещенных коэффициентов, которая включает в себя вектор исходных коэффициентов добавлением одного или нескольких значений смещения к коэффициенту DC матрицы масштабированных коэффициентов, и средство для формирования матрицы промежуточных коэффициентов с использованием последовательности операций структуры бабочки для применения преобразования к каждой вектор-строке в матрице смещенных коэффициентов,
средство для формирования матрицы преобразованных коэффициентов с использованием последовательности операций структуры бабочки для применения преобразования к каждому вектор-столбцу в матрице промежуточных коэффициентов, и
средство для формирования матрицы значений компонента пикселя посредством сдвига вправо коэффициентов в матрице преобразованных коэффициентов на первое значение,
причем или средство для формирования матрицы промежуточных коэффициентов, или средство для формирования матрицы преобразованных коэффициентов содержит средство для использования последовательности операций структуры бабочки для применения преобразования к вектору исходных коэффициентов.
37. Устройство по п.36,
в котором средство для формирования матрицы смещенных коэффициентов содержит средство для добавления значения смещения центра к коэффициенту DC матрицы масштабированных коэффициентов,
причем значение смещения центра равно 2(P+T-1), где P равно первому значению, и T является количеством битов, добавляемых выполнением преобразования.
38. Устройство по п.36,
в котором средство для формирования матрицы смещенных коэффициентов содержит средство для добавления значения дополнительного смещения к коэффициенту DC матрицы масштабированных коэффициентов,
в котором добавление значений дополнительного смещения к коэффициенту DC делает положительные ошибки и отрицательные ошибки, в среднем, равными по величине и, в среднем, симметричными относительно нуля, и
в котором ошибки представляют разности между значениями, которые получаются в результате сдвига вправо представлений коэффициентов с фиксированной запятой ограниченной точности в матрице преобразованных коэффициентов на первую величину, и результатами от деления коэффициентов в матрице преобразованных коэффициентов на 2P, где P равно первой величине, без учета точности.
39. Устройство по п.38, в котором значение дополнительного смещения равно -1, когда коэффициент DC является отрицательным, и равно 0, когда коэффициент DC является неотрицательным.
40. Устройство по п.38,
причем устройство также содержит средство для выбора на псевдослучайной основе значения, которое равно или -1 или 0, и
причем средство для добавления значения дополнительного смещения добавляет выбранное значение как значение дополнительного смещения.
41. Устройство по п.36,
в котором средство для формирования матрицы масштабированных коэффициентов содержит средство для масштабирования каждого коэффициента в матрице входных коэффициентов посредством сдвига влево каждого из коэффициентов в матрице входных коэффициентов на второе значение,
в котором средство для использования последовательности операций структуры бабочки для применения преобразования вызывает включение в каждый коэффициент в матрице преобразованных коэффициентов количества дополнительных битов точности, измеряемого третьим значением, и
в котором первое значение равно второму значению плюс третье значение.
42. Устройство по п.41, в котором второе значение равно количеству битов мантиссы чисел с фиксированной запятой, используемых при применении преобразования.
43. Устройство по п.42,
в котором вторым значением является три, и
в котором, с учетом матрицы входных коэффициентов, значения компонента пикселя удовлетворяют требованиям по точности стандарта 1180 Института инженеров по электротехнике и радиоэлектронике (IEEE).
44. Устройство по п.30,
причем устройство также содержит средство для создания пикселей, которые включают в себя значение компонента пикселя в матрице значений компонента пикселя, и
причем устройство также содержит средство, предписывающее блоку отображения отображать пиксели.
45. Устройство по п.30, в котором числа с фиксированной запятой являются 16-разрядными числами с фиксированной запятой.
46. Машиночитаемый носитель информации, содержащий команды, которые при исполнении вызывают в процессоре
использование последовательности операций структуры бабочки над числами с фиксированной запятой для применения преобразования к вектору коэффициентов для формирования вектора преобразованных коэффициентов,
причем преобразованные коэффициенты в векторе преобразованных коэффициентов являются аппроксимациями значений, которые формируются преобразованием вектора исходных коэффициентов с использованием идеального обратного дискретного косинусного преобразования,
вызов вывода звуковых или оптических сигналов блоком воспроизведения мультимедиа на основе преобразованных значений в векторе преобразованных значений,
причем разности между результатами, сформированными одной из операций структуры бабочки, и результатами, которые формируются эквивалентной операцией структуры бабочки с использованием арифметических операций с неограниченной точностью, сосредоточены вокруг нуля, и положительные разности, и отрицательные разности имеют приблизительно равное значение.
47. Машиночитаемый носитель информации по п.46, в котором команды, которые вызывают выполнение процессором операций структуры бабочки, вызывают выполнение процессором операции структуры бабочки вида
u=((x*C)>>k)-((y*-S)>>k'),
v=((x*S)>>k')-((y*C)>>k),
где u и v - получающиеся в результате числа с фиксированной запятой,
где C, S, k и k' - постоянные целые числа,
где x и y - переменные с фиксированной запятой, и
где C/2k и S/2k - аппроксимации рациональным числом иррациональных констант.
48. Машиночитаемый носитель информации по п.47,
в котором вектор исходных коэффициентов состоит из восьми коэффициентов: x0, x1, x2, x3, x4, x5, x6 и x7,
в котором вектор преобразованных коэффициентов состоит из восьми коэффициентов: z0, z1, z2, z3, z4, z5, z6 и z7,
в котором команды, которые вызывают использование процессором последовательности операций структуры бабочки, вызывают в программируемом процессоре:
выполнение первой операции структуры бабочки, в которой x=x0, y=x4, C=1, S=1, u=x0', v=x4',
выполнение второй операции структуры бабочки, в которой x=x2, y=x6, C=α, S=β, u=x6' и v=x2',
выполнение третьей операции структуры бабочки, в которой x=x7, y=x1, C=1, S=1, u=x7' и v=x1',
выполнение четвертой операции структуры бабочки, в которой x=*x1', y=x5, C=1, S=1, u=x1'' и v=x5',
выполнение пятой операции структуры бабочки, в которой x=*x7', y=x3, C=1, S=1, u=x7'' и v=x3',
выполнение шестой операции структуры бабочки, в которой x=x0', y=x6', C=1, S=1, u=x0'' и v=x6'',
выполнение седьмой операции структуры бабочки, в которой x=x4', y=x2', C=1, S=1, u=x4'' и v=x2'',
выполнение восьмой операции структуры бабочки, в которой x=x1'', y=x7'', C=ζ, S=ε, u= x1''' и v=x7''',
выполнение девятой операции структуры бабочки, в которой x=x3', y=x5', C=δ, S=γ, u=x5'' и v=x3''
выполнение десятой операции структуры бабочки, в которой x=x0'', y=x7''', C=1, S=1, u=z0 и v=z7,
выполнение одиннадцатой операции структуры бабочки, в которой x=x4'', y=x5'', C=1, S=1, u=z1 и v=z6,
выполнение двенадцатой операции структуры бабочки, в которой x=x2'', y=x3'', C=1, S=1, u=z2 и v=z5, и
выполнение тринадцатой операции структуры бабочки, в которой x=x6'', y=x1''', C=1, S=1, u=z3 и v=z4.
49. Машиночитаемый носитель информации по п.48, в котором α, β, γ, δ, ε и ζ являются аппроксимациями иррациональных значений , , и, соответственно.
50. Машиночитаемый носитель информации по п.49, в котором α=8867/16384, β=21407/16384, γ=5681/4096, δ=565/2048, ε=9633/8192, ζ=12873/16384.
51. Машиночитаемый носитель информации по п.47, в котором команды, которые вызывают использование процессором последовательности операции структуры бабочки, вызывают умножение программируемым процессором значений в операции структуры бабочки с использованием последовательности операций сдвига, сложения и вычитания, в результате которых получаются значения, которые аппроксимируют значения, которые получаются в результате выполнения операций умножения.
52. Машиночитаемый носитель информации по п.46, в котором команды также вызывают в программируемом процессоре
формирование матрицы масштабированных коэффициентов посредством масштабирования каждого коэффициента в матрице входных коэффициентов,
формирование матрицы смещенных коэффициентов, которая включает в себя вектор исходных коэффициентов добавлением одного или нескольких значений смещения к коэффициенту DC матрицы масштабированных коэффициентов,
использование последовательности операций структуры бабочки над числами с фиксированной запятой для применения преобразования к каждой вектор-строке в матрице коэффициентов для формирования матрицы промежуточных коэффициентов,
использование последовательности операций структуры бабочки над числами с фиксированной запятой для применения преобразования к каждому вектор-столбцу в матрице промежуточных коэффициентов для формирования матрицы преобразованных коэффициентов, и
формирование матрицы значений компонента пикселя посредством сдвига вправо коэффициентов в матрице преобразованных коэффициентов на первое значение.
53. Машиночитаемый носитель информации по п.52,
в котором команды, которые вызывают формирование процессором матрицы смещенных коэффициентов, вызывают добавление процессором значения смещения центра к коэффициенту DC матрицы масштабированных коэффициентов, и
в котором значение смещения центра равно 2(P+T-1), где P равно первому значению, и T является количеством битов, добавляемых выполнением преобразования.
54. Машиночитаемый носитель информации по п.52,
в котором команды, которые вызывают формирование процессором матрицы смещенных коэффициентов, вызывают добавление процессором значения дополнительного смещения к коэффициенту DC матрицы масштабированных коэффициентов,
причем добавление значения дополнительного смещения к коэффициенту DC вызывает положительные ошибки и отрицательные ошибки, в среднем, равными по величине и, в среднем, симметричными относительно нуля, и
причем упомянутые ошибки представляют разности между значениями, которые получаются в результате сдвига вправо представлений коэффициентов с фиксированной запятой ограниченной точности в матрице преобразованных коэффициентов на первую величину, и результатами от деления коэффициентов в матрице преобразованных коэффициентов на 2P, где P равно первой величине, без учета точности.
55. Машиночитаемый носитель информации по п.54, в котором значение дополнительного смещения равно -1, когда коэффициент DC является отрицательным, и равно 0, когда коэффициент DC является неотрицательным.
56. Машиночитаемый носитель информации по п.54,
в котором команды также вызывают выбор процессором, на псевдослучайной основе, значения, которое равно или -1 или 0, и
в котором команды, которые вызывают добавление процессором значения дополнительного смещения, вызывают добавление процессором выбранного значения как значения дополнительного смещения.
57. Машиночитаемый носитель информации по п.52,
в котором команды, которые вызывают формирование процессором матрицы масштабированных коэффициентов, вызывают сдвиг влево процессором каждого коэффициента в матрице входных коэффициентов на второе значение,
в котором команды, которые вызывают использование процессором последовательности операций структуры бабочки, вызывают включение в каждый коэффициент в матрице преобразованных коэффициентов количества дополнительных битов точности, измеряемого третьим значением, и
в котором первое значение равно второму значению плюс третье значение.
58. Машиночитаемый носитель информации по п.57, в котором второе значение равно количеству битов мантиссы чисел с фиксированной запятой, используемых при применении преобразования.
59. Машиночитаемый носитель информации по п.58,
в котором вторым значением является три, и
в котором, с учетом матрицы входных коэффициентов, значения компонента пикселя удовлетворяют требованиям по точности стандарта 1180 Института инженеров по электротехнике и радиоэлектронике (IEEE).
60. Машиночитаемый носитель информации по п.52, в котором команды также вызывают в процессоре
создание пикселей, которые включают в себя значения компонента пикселя в матрице значений компонента пикселя, и
отображение пикселей на блоке отображения.
61. Машиночитаемый носитель информации по п.46, в котором числа с фиксированной запятой являются 16-разрядными числами с фиксированной запятой.
Applications Claiming Priority (8)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| US81669706P | 2006-06-26 | 2006-06-26 | |
| US60/816,697 | 2006-06-26 | ||
| US84136206P | 2006-08-30 | 2006-08-30 | |
| US60/841,362 | 2006-08-30 | ||
| US60/847,194 | 2006-09-25 | ||
| US82966906P | 2006-10-16 | 2006-10-16 | |
| US60/829,669 | 2006-10-16 | ||
| US60/869,530 | 2006-12-11 |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| RU2009102250A true RU2009102250A (ru) | 2010-08-10 |
| RU2439682C2 RU2439682C2 (ru) | 2012-01-10 |
Family
ID=42698399
Family Applications (2)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| RU2009102248/08A RU2419855C2 (ru) | 2006-06-26 | 2007-06-25 | Снижение ошибок в ходе вычисления обратного дискретного косинусного преобразования |
| RU2009102250/08A RU2439682C2 (ru) | 2006-06-26 | 2007-06-26 | Уменьшение ошибок во время вычисления обратного дискретного косинусного преобразования |
Family Applications Before (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| RU2009102248/08A RU2419855C2 (ru) | 2006-06-26 | 2007-06-25 | Снижение ошибок в ходе вычисления обратного дискретного косинусного преобразования |
Country Status (1)
| Country | Link |
|---|---|
| RU (2) | RU2419855C2 (ru) |
Families Citing this family (8)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CA2862282C (en) * | 2012-02-29 | 2021-03-30 | Sony Corporation | Image processing device and method |
| WO2013175698A1 (ja) * | 2012-05-25 | 2013-11-28 | パナソニック株式会社 | 画像符号化方法、画像符号化装置、画像復号方法、画像復号装置および画像符号化復号装置 |
| WO2013175736A1 (ja) | 2012-05-25 | 2013-11-28 | パナソニック株式会社 | 動画像符号化方法、動画像符号化装置、動画像復号方法、動画像復号装置、および、動画像符号化復号装置 |
| PL2858354T3 (pl) | 2012-05-25 | 2023-05-02 | Sun Patent Trust | Sposób kodowania obrazów wideo, sposób dekodowania obrazów wideo, urządzenie do kodowania obrazów wideo, urządzenie do dekodowania obrazów wideo oraz urządzenie do kodowania-dekodowania obrazów wideo |
| AU2013273044B2 (en) | 2012-06-04 | 2016-09-15 | Sun Patent Trust | Video image encoding method, video image encoding device, video image decoding method, and video image decoding device |
| FR2993084A1 (fr) * | 2012-07-09 | 2014-01-10 | France Telecom | Procede de codage video par prediction du partitionnement d'un bloc courant, procede de decodage, dispositifs de codage et de decodage et programmes d'ordinateur correspondants |
| JP6315911B2 (ja) | 2013-07-09 | 2018-04-25 | キヤノン株式会社 | 画像符号化装置、画像符号化方法及びプログラム、画像復号装置、画像復号方法及びプログラム |
| RU2737343C2 (ru) * | 2019-01-10 | 2020-11-27 | Федеральное государственное казенное военное образовательное учреждение высшего образования "Военный учебно-научный центр Военно-воздушных сил "Военно-воздушная академия имени профессора Н.Е. Жуковского и Ю.А. Гагарина" (г. Воронеж) Министерства обороны Российской Федерации | Способ определения характера движения объекта на кадрах видеопоследовательности |
Family Cites Families (6)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| TW224553B (en) * | 1993-03-01 | 1994-06-01 | Sony Co Ltd | Method and apparatus for inverse discrete consine transform and coding/decoding of moving picture |
| US5701263A (en) * | 1995-08-28 | 1997-12-23 | Hyundai Electronics America | Inverse discrete cosine transform processor for VLSI implementation |
| US5754456A (en) * | 1996-03-05 | 1998-05-19 | Intel Corporation | Computer system performing an inverse cosine transfer function for use with multimedia information |
| DE59801516D1 (de) * | 1997-01-31 | 2001-10-25 | Siemens Ag | Verfahren und anordnung zur codierung und decodierung eines digitalisierten bildes |
| US6587590B1 (en) * | 1998-02-02 | 2003-07-01 | The Trustees Of The University Of Pennsylvania | Method and system for computing 8×8 DCT/IDCT and a VLSI implementation |
| US6859815B2 (en) * | 2000-12-19 | 2005-02-22 | Koninklijke Philips Electronics N.V. | Approximate inverse discrete cosine transform for scalable computation complexity video and still image decoding |
-
2007
- 2007-06-25 RU RU2009102248/08A patent/RU2419855C2/ru not_active IP Right Cessation
- 2007-06-26 RU RU2009102250/08A patent/RU2439682C2/ru not_active IP Right Cessation
Also Published As
| Publication number | Publication date |
|---|---|
| RU2439682C2 (ru) | 2012-01-10 |
| RU2419855C2 (ru) | 2011-05-27 |
| RU2009102248A (ru) | 2010-08-10 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| RU2009102250A (ru) | Уменьшение ошибок во время вычисления обратного дискретного косинусного преобразования | |
| JP4560033B2 (ja) | ビデオまたはイメージのデータを復号化するための方法 | |
| JP5113067B2 (ja) | 信号およびデータ処理のための効率的な無乗算計算 | |
| KR101131757B1 (ko) | 스케일링 인터페이스 및 넌-스케일링 인터페이스를 갖는 변환 디자인 | |
| JP5086274B2 (ja) | 共通因数を用いる変換 | |
| US20080208945A1 (en) | Method to compute an approximation to the reciprocal of the square root of a floating point number in ieee format | |
| WO1999059080A1 (en) | Method and apparatus for determining discrete cosine transforms | |
| JP2017533458A5 (ru) | ||
| Tyler et al. | AltiVec/sup TM: bringing vector technology to the PowerPC/sup TM/processor family | |
| JP3577325B2 (ja) | 離散余弦変換（ｄｃｔ）によるデータ処理方法、ｄｃｔ方法、およびｄｃｔデータ処理回路 | |
| JP4965711B2 (ja) | 符号対称の丸め誤差を有する２進分数による積の高速計算 | |
| KR101722215B1 (ko) | 이산 여현 변환 장치 및 방법 | |
| CN103365826B (zh) | 一种小面积的基-3fft蝶形单元 | |
| JP5589628B2 (ja) | 内積演算装置および内積演算方法 | |
| JP4933405B2 (ja) | データ変換装置及びその制御方法 | |
| RU2009102254A (ru) | Эффекивные аппроксимации с фиксированной запятой прямого и обратного дискретных косинусных преобразований | |
| US6549924B1 (en) | Function generating interpolation method and apparatus | |
| RU2009102255A (ru) | Эффективные аппроксимации с фиксированной запятой для прямых и обратных дискретных косинусных преобразований | |
| KR100240002B1 (ko) | 영상신호의 압축과 복원을 위한 이산 코사인 변환 장치 | |
| TWI432029B (zh) | 具有比例化及非比例化介面之變換設計 | |
| CN117372495A (zh) | 一种加速数字图像处理中不同位宽点积的计算方法 | |
| JP2007079972A (ja) | 逆変換回路 | |
| US20050210090A1 (en) | Logarithm determining method and apparatus for the same | |
| JPH08212193A (ja) | データ変換方式並びに装置とそれを利用したデータ転送方式並びに装置 | |
| TW201229786A (en) | Multiple-use matrix multiplication computer program and application thereof |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| MM4A | The patent is invalid due to non-payment of fees |
Effective date: 20190627 |