Memory structure to minimize rounding/trunction errors for n-dimensional image transformation

Claim 3

The method recited in claim 1 further comprising the step of performing a second transformation, of the multiple dimension transform, on the output set of data elements and said set of input data elements so as to form a second array of transformed data elements and then repeating the steps (c) to (g) inclusive.

Claim 4

The method recited in claim 1 wherein the steps (a) through (g) are performed for a plurality of sets of input data elements, said method further comprising of aligning the output sets of data elements for each set of the input data elements.

Claim 5

A memory architecture which minimizes rounding/truncation errors in the storage of multiple dimension transform data comprising: first storage means for temporarily storing an array of transformed data elements, each of the transformed data elements having a larger number of bits than that of an input set of data elements; a bit range representation adjuster connected to receive said array of transformed data elements from said first storage means for determining a common range of the transformed data elements; shift and round/truncate logic connected to said bit range representation adjuster for first determining a minimum number of bits required to represent the common range without loss of information and shifting said data array to said minimum number of bits and second rounding or truncating low order bits of said minimum number of bits so as to reduce the array to a memory word size available for storage; and second storage means for receiving and storing the rounded/truncated array of data.

Claim 6

A memory architecture which minimizes rounding/truncation errors in the storage of multiple dimension transform data comprising: first storage means for temporarily storing an array of transformed data elements, each of the transformed data elements having a larger number of bits than that of an input set of data elements; a bit range representation adjuster connected to receive said array of transformed data elements from said first storage means for determining a common range of the transformed data elements; shift and round/truncate logic connected to said bit range representation adjuster for first determining a minimum number of bits required to represent the common range without loss of information and shifting said data array to said minimum number of bits and second rounding or truncating low order bits of said minimum number of bits so as to reduce the array to a memory word size available for storage; and second storage means for receiving and storing the rounded/truncated array of data.

Claim 7

The memory architecture recited in claim 4 wherein said bit range representation adjuster comprises logic which successively compares first and second, second and third, third and fourth, and so forth leading bits of each of said transformed data elements stored in said first storage means, said logic stopping the comparison when a transition in logic level is detected in any of the comparisons.

Claim 8

A multiple dimensional image data transformation system comprising: means for storing a set of input image data elements; a plurality of one dimensional transformation circuits, a first one of the transformation circuits being connected to said means for storing to receive said set of input image data elements and performing a transformation operation to produce an array of transformed data elements, each of the transformed data elements having a larger number of bits than the input data elements; a transpose memory between each pair of one dimensional transformation circuits, each said transpose memory comprising: first storage means for temporarily storing an array of transformed data elements, each of the transformed data elements having a larger number of bits than an input set of data elements; a bit range representation adjuster connected to receive said array of transformed data elements from said first storage means for determining a common range of the transformed data elements; shift and round/truncate logic connected to said bit range representation adjuster for first determining a minimum number of bits required to represent the common range without loss of information and shifting said data array to said minimum number of bits and second rounding or truncating low order bits of said minimum number of bits so as to reduce the array to a memory word size available for storage; and second storage means for receiving and storing the rounded/truncated array of data; each transformation circuit after the first transformation circuit being connected to said means for storing to receive said set of input image data elements and to a preceding transpose memory to receive rounded/truncated array data and performing a transformation operation to produce another array of transformed data elements, each of the transformed data elements having a larger number of bits than the input data elements.

Claim 9

A multiple dimensional image data transformation system comprising: means for storing a set of input image data elements; a plurality of one dimensional transformation circuits, a first one of the transformation circuits being connected to said means for storing to receive said set of input image data elements and performing a transformation operation to produce an array of transformed data elements, each of the transformed data elements having a larger number of bits than the input data elements; a transpose memory between each pair of one dimensional transformation circuits, each said transpose memory comprising: first storage means for temporarily storing an array of transformed data elements, each of the transformed data elements having a larger number of bits than an input set of data elements; a bit range representation adjuster connected to receive said array of transformed data elements from said first storage means for determining a common range of the transformed data elements; shift and round/truncate logic connected to said bit range representation adjuster for first determining a minimum number of bits required to represent the common range without loss of information and shifting said data array to said minimum number of bits and second rounding or truncating low order bits of said minimum number of bits so as to reduce the array to a memory word size available for storage; and second storage means for receiving and storing the rounded/truncated array of data; each transformation circuit after the first transformation circuit being connected to said means for storing to receive said set of input image data elements and to a preceding transpose memory to receive rounded/truncated array data and performing a transformation operation to produce another array of transformed data elements, each of the transformed data elements having a larger number of bits than the input data elements.

Claim 10

The multiple dimensional image data transformation system recited in claim 6 wherein said bit range representation adjuster comprises logic which successively compares first and second, second and third, third and fourth, and so forth leading bits of each of said transformed data elements stored in said first storage means, said logic stopping the comparison when a transition in logic level is detected in any of the comparisons.