US 2006/0039626 A1Published application

Data transformation apparatus and method

AssigneeCanon Kabushiki Kaisha

InventorTadayoshi Nakayama

Life of this patent

Estimating the term…

Loading patent…

Abstract

The present invention performs a lossless four-point orthogonal transformation with reduced rounding errors using a simple configuration. It provides a data transformation apparatus which receives four items of vector data X0, X1, X2, and X3 expressed in terms of integers and obtains transformed data expressed in terms of integers by application of a coefficient “a” that is an odd number larger than 1 using a matrix operation: ( Y 0 Y 1 Y 2 Y 3 ) = 1 1 + a 2 ⁢ ( 1 a a a 2 a - 1 a 2 - a a a 2 - 1 - a a 2 - a - a 1 ) ⁢ ( X 0 X 1 X 2 X 3 ) First, the data transformation apparatus determines D0 to D3 (assuming a=3): D0=X0+3X1+3X2+9X3 D1=3X0−X1+9X2−3X3 D2=3X0+9X1−X2−3X3 D3=9X0−3X1−3X2+X3 Next, it determines E1 by adding integer data smaller than half a divisor {1+a2} to D1 and determines correction data E0, E2, and E4 by adding a value equal to half the divisor to the rest of the data D0, D2, and D3. Next, it divides E0 to E4 by the divisor and outputs resulting data Y0, Y1, Y2, and Y3.

Claims10

Dependent claims

A data transformation apparatus which receives four items of vector data X0, X1, X2, and X3 expressed in terms of integers and obtains transformed data expressed in terms of integers by application of a coefficient “a” that is an odd number larger than 1 using a matrix operation:

1
1
+
a
2
⁢
(
1
a
a
a
2
a
-
1
a
2
-
a
a
a
2
-
1
-
a
a
2
-
a
-
a
1
)
⁢
(
X
0
X
1
X
2
X
3
)
the data transformation apparatus comprising:
holding means for receiving and holding the coefficient a and the vector data X0, X1, X2, and X3;
first computational means for performing an operation D0=X0+aX1+aX2+a2X3;
second computational means for performing an operation D1=aX0−X1+a2X2−aX3;
third computational means for performing an operation D2=aX0+a2X1−X2−aX3;
fourth computational means for performing an operation D3=a2X0−aX1−aX2+X3;
allocation means for allocating the coefficient a and the vector data X0, X1, X2, and X3 held by the holding means to the first to fourth computational means;
corrective computational means for adding integer data smaller than half a divisor (1+a2) to at least one item of the data D0, D1, D2, and D3 obtained by the first to fourth computational means and adding a value equal to half the divisor {1+a2} to the rest of the data, and thereby calculating correction data D0′, D1′, D2′, and D3′ to be divided;
and
output means for dividing the correction data D0′, D1′, D2′, and D3′ obtained by the corrective computational means by the divisor, rounding results of division in such a way that resulting integers will be smaller than the results of division, and outputting the resulting integers as transformed data.

52 more elements

A data transformation apparatus which receives four items of vector data X0, X1, X2, and X3 expressed in terms of integers with m significant bits and obtains transformed data Y0, Y1, Y2, and Y3 expressed in terms of integers with m significant bits by application of a coefficient “a” that is an odd number larger than 1 using a matrix operation:

1
1
+
a
2
⁢
(
1
a
a
a
2
a
-
1
a
2
-
a
a
a
2
-
1
-
a
a
2
-
a
-
a
1
)
⁢
(
X
0
X
1
X
2
X
3
)
the data transformation apparatus comprising:
holding means for receiving and holding the coefficient a and the vector data X0, X1, X2, and X3;
first preliminary computational means for computing an integer quotient R0 by dividing 2n by a divisor {1+a2}, where n is the number of significant bits;
second preliminary computational means for computing a value R1 by adding 1 to the quotient determined by the first computational means;
third preliminary computational means for computing an offset value based on the coefficient a and m;
first computational means for performing an operation D0=X0+aX1+aX2+a2X3;
second computational means for performing an operation D1=aX0−X1+a2X2−aX3;
third computational means for performing an operation D2=aX0+a2X1−X2−aX3;
fourth computational means for performing an operation D3=a2X0−aX1−aX2+X3;
allocation means for allocating the coefficient a and the vector data X0, X1, X2, and X3 held by the holding means to the first to fourth computational means;
first adding means for adding half the divisor to the data D0, D1, D2, and D3 obtained by the first to fourth computational means;
second adding means for adding the offset value obtained by the third preliminary computational means to three of the data items outputted by the first adding means;
multiplication means for multiplying at least one of the data outputted from the second adding means by the value R1 and multiplying the rest of the data by the value R0;
shifting means for shifting multiplication results produced by the multiplication means n bits to the right in order to divide the multiplication results by 2n;
and
subtracting means for subtracting a value corresponding to the offset from the data processed by the second adding means among the values obtained by the shifting means.

58 more elements

A data transformation method which receives four items of vector data X0, X1, X2, and X3 expressed in terms of integers with m significant bits and obtains transformed data Y0, Y1, Y2, and Y3 expressed in terms of integers with m significant bits by application of a coefficient “aa” that is an odd number larger than 1 using a matrix operation:

1
1
+
a
2
⁢
(
1
a
a
a
2
a
-
1
a
2
-
a
a
a
2
-
1
-
a
a
2
-
a
-
a
1
)
⁢
(
X
0
X
1
X
2
X
3
)
the data transformation method comprising:
a holding step of receiving and holding the coefficient a and the vector data X0, X1, X2, and X3;
a first preliminary computational step of computing an integer quotient R0 by dividing 2n by a divisor (1+a2), where n is the number of significant bits;
a second preliminary computational step of computing a value R1 by adding 1 to the quotient determined by the first computational step;
a third preliminary computational step of computing an offset value based on the coefficient a and m;
a first computational step of performing an operation D0=X0+aX1+aX2+a2X3;
a second computational step of performing an operation D1=aX0−X1+a2X2−aX3;
a third computational step of performing an operation D2=aX0+a2X1−X2−aX3;
a fourth computational step of performing an operation D3=a2X0−aX1−aX2+X3;
an allocation step of allocating the coefficient a and the vector data X0, X1, X2, and X3 held by the holding step to the first to fourth computational step;
a first adding step of adding half the divisor to the data D0, D1, D2, and D3 obtained by the first to fourth computational step;
a second adding step of adding the offset value obtained by the third preliminary computational step to three of the data items outputted by the first adding step;
a multiplication step of multiplying at least one of the data outputted from the second adding step by the value R1 and multiplying the rest of the data by the value R0;
a shifting step of shifting multiplication results produced by the multiplication step n bits to the right in order to divide the multiplication results by 2n;
and
a subtracting step of subtracting a value corresponding to the offset from the data processed by the second adding step among the values obtained by the shifting step.

58 more elements

Dependencies are inferred from the claim text.