Pipeline synthetic aperture radar data compression utilizing systolic binary tree-searched architecture for vector quantization

In a systolic-array image processing system, a tree-searched vector quantizer for image data compression comprising a series of L systolic arrays of N.sub.l identical processors, and a plurality L of levels of subcodebooks, where l is the tree level index from 1 to L, one level of subcodebooks for each of L systolic arrays, and means for successively comparing an input vector sequence x.sup.[k] with stored codevectors in subcodebook levels in search for an output coded data sequence i.sup.[k] of minimum distortion in accordance with the following equations:

• ##EQU12## where x.sup.[k] is an input data vector sequence, k represents the time index of said sequence, and the codevector notation is:
• C.sub.i.sbsb.1 for level 1;
• C.sub.i.sbsb.1.sub.i.sbsb.2 for level 2;
• and so forth with C.sub.i.sbsb.1.sub.i.sbsb.2 . . . .sub.i.sbsb.L for level L, and i.sub.1 is a codevector index for tree level-1 subcodebook i.sub.1, i.sub.2 . . . i.sub.L is a codevector index for tree level-L subcodebook, D(x.sup.[k] C.sub.i . . . ) is a distortion function, and i.sup.[k] is a vector quantization coded output data sequence of said input vector sequence for binary tree level-l encoding process, N.sub.l -1 is the maximum value of said vector coded output data for tree level l, 1.ltoreq.l.ltoreq.L.

In a systolic-array image processing system, a binary tree-searched raw codebook vector quantizer for image data compression comprising a series of n systolic arrays of two identical processors and a plurality n of levels of subcodebooks, one level of subcodebooks for each systolic array for successively comparing an input vector sequence x.sup.[k] with selected codevector pairs in subcodebook levels in accordance with the following equations:

• i.sub.1.sup.[k] =min.sup.-1 D(x.sup.[k],C.sub.i.sbsb.1), i.sub.1 =0,1
• i.sub.2.sup.[k] =min.sup.-1 D(x.sup.[k],C.sub.i.sbsb.1.sub.i.sbsb.2), i.sub.2 =0,1
• i.sub.n.sup.[k] =min.sup.-1 D(x.sup.[k],C.sub.i.sbsb.1.sub.i.sbsb.2 .sub.. . . i.sbsb.n-1.sub.i.sbsb.n), i.sub.n =0,1
• i.sup.[k] =i.sub.1.sup.[k] i.sub.2.sup.[k] . . . i.sub.n.sup.[k]
• where x.sup.[k] is an input vector sequence and k represents the time index of said sequence, and the codevector notation is:
• C.sub.i.sbsb.1 for binary level 1, C.sub.i.sbsb.1.sub.i.sbsb.2 for binary level 2, and so forth with C.sub.i.sbsb.1.sub.i.sbsb.2 .sub.. . . i.sbsb.n for level n, i.sub.1 is codevector index for binary tree level-1 subcodebook, i.sub.1 i.sub.2 is codevector index for binary tree level-2 subcodebook, and so forth i.sub.1 i.sub.2 . . . i.sub.n is codevector index for binary tree level-n subcodebook, n is the level number of the deepest binary tree, D(x.sup.[k],C . . . ) is a distortion function, i.sub.l.sup.[k] is a vector quantization coded output data sequence of said input vector sequence for binary tree level-l encoding process and l is a binary tree level index from 1 to n, i.sup.[k] is a vector quantization coded output data sequence of said input vector sequence for overall encoding process.

In a systolic-array image processing system, a binary tree-searched difference codebook vector quantizer for image date compression comprising a series of systolic arrays of identical processors and a plurality of levels of subcodebooks, one level of subcodebooks for each systolic array for successively comparing an input vector with selected codevector pair difference in subcodebook levels in accordance with the following equations:

• i.sub.1.sup.[k] =min.sup.-1 D(x.sup.[k],C.sub.i.sbsb.1), i.sub.1 =0,1
• i.sub.2.sup.[k] =min.sup.-1 D(x.sup.[k],C.sub.i.sbsb.1.sub.i.sbsb.2), i.sub.2 =0,1
• i.sub.n.sup.[k] =min.sup.-1 D(x.sup.[k],C.sub.i.sbsb.1.sub.i.sbsb.2 .sub.. . . i.sbsb.n-1.sub.i.sbsb.n), i.sub.n =0,1
• i.sup.[k] =i.sub.1.sup.[k] i.sub.2.sup.[k] . . . i.sub.n.sup.[k]
• where x.sup.[k] is an input vector sequence and k represents the time index of said sequence, and the codevector notation is:
• C.sub.i.sbsb.1 for binary level 1, C.sub.i.sbsb.1.sub.i.sbsb.2 for binary level 2, and so forth with C.sub.i.sbsb.1.sub.i.sbsb.2 .sub.. . . i.sbsb.n for level n, i.sub.1 is codevector index for binary tree level-1 subcodebook, i.sub.1 i.sub.2 is codevector index for binary tree level-2 subcodebook, and so forth i.sub.1 i.sub.2 . . . i.sub.n is codevector index for binary tree level-n subcodebook, n is the level number of the deepest binary tree, D(x.sup.[k],C . . . ) is a distortion function, i.sub.1.sup.[k] is a vector quantization coded output data sequence of said input vector sequence for binary tree level-1 encoding process, i.sup.[k] is a vector quantization coded output data sequence of said input vector sequence for overall encoding process, wherein said distortion function between an input vector x.sup.[k] and codevectors at the same binary tree level C.sub.0 and C.sub.1 are ##EQU13## x.sup.[k] (j) being the j.sup.th component of the input vector, j being the component index of the input vector, m being the number of component of the input vector, C.sub.i (j) being the j.sup.th component of the i.sup.th codevector, i being the codevector index of the codebook, C.sub.0 and C.sub.1 being the codevector pair of the subcodebook in the same binary tree level, where codebook memory size is (2.sup.n+1 -2)nK bits, n is a maximum number of tree levels, K is a number of bits per pixel, said distortion computation between input vector x.sup.[k] and codevectors at the same binary tree level C.sub.0 and C.sub.1 is simplified as follows:
• ##EQU14## and instead of saving C.sub.0 (j) and C.sub.1 (j), the terms, ##EQU15## and .delta.(j)=C.sub.0 (j)-C.sub.1 (j) are stored in said codebook, where codebook memory size is (2.sup.n -1) [m(K+1)+(2K+log m)] bits.