Method and apparatus for effectively performing linear transformations

[0001] The present invention relates to the fields of digital signal processing. It introduces an improved method and apparatus for performing linear transformations, with reduced number of arithmetic operations, simplified circuitry, and low power consumption.

[0002] Linear transformations are commonly used for signal or data processing. A linear transformation produce from an n-dimensional vector, considered as “input vector” an r-dimensional vector, considered as “output vector”. In many applications the input vector consists of digital samples of a given signal that requires processing. However applications of linear transformations are not restricted to any specific domain, they are essential to every field of science and technology and their efficient performance is highly desirable.

[0003] A general linear transformation from the set of n-dimensional vectors (real, complex or from any field of scalars) to the set of r-dimensional vectors (over the same field of scalars), may be represented by a matrix of order rxn given by: $A=[\begin{array}{cccc}{a}_{11}& a_{12}& \dots & a_{1n}\\ a_{21}& a_{22}& \dots & a_{2n}\\ ⋮& & & \\ a_{\mathrm{r1}}& & & a_{\mathrm{rn}}\end{array}]$

[0004] A general input n-dimensional column vector is written in the following form: $x=[\begin{array}{c}{x}_1\\ x_2\\ ⋮\\ x_n\end{array}]$

[0005] The linear transformation produce from the input vector x an output column vector, y of dimension r, through the product of the matrix by the vector which is given by following formula: $y=[\begin{array}{c}{y}_1\\ y_2\\ ⋮\\ y_r\end{array}]=[\begin{array}{cccc}{a}_{11}& a_{12}& \dots & a_{1n}\\ a_{21}& a_{22}& \dots & a_{2n}\\ ⋮& & & \\ a_{\mathrm{r1}}& & & a_{\mathrm{rn}}\end{array}][\begin{array}{c}{x}_1\\ x_2\\ ⋮\\ x_n\end{array}]=[\begin{array}{cccc}{a}_{11}{x}_1+& a_{12}{x}_2+& \dots & +a_{1n}{x}_n\\ a_{21}{x}_1+& a_{22}{x}_2+& \dots & +a_{2n}{x}_n\\ ⋮& ⋮& & ⋮\\ a_{\mathrm{r1}}{x}_1& a_{\mathrm{r2}}{x}_2+& \dots & +a_{\mathrm{rn}}{x}_n\end{array}]$

[0006] A straightforward performance of the linear transformation requires, r·n products and r·(n−1) additions.

[0007] Binary matrix are of special importance in the development and application of the present invention. Binary-bipolar matrix are those containing only ±1 values in their entries. Henceforth they would be called U-matrix. A linear transformation represented by a U-matrix will be called U-transformation. In the above presentation, if the given transformation is a U-transformation then r·(n−1) additions/subtractions would be required for its straightforward performance. Another type of binary matrix are those containing only 0,1 values in their entries. They would be called 0-1-matrix. A linear transformation represented by 0-1-matrix is called a 0-1-transformation. In the above presentation, r·(n−1)/2 additions would be required, on average, for a straightforward performance of a 0-1-transformation.

[0008] In the current text the term “binary transformation” would consist of the two types of transformations mentioned above: U-transformations and 0-1-transformations. To complete the terminology-introduction it would be mentioned that the term U-vector would refer to a vector having ±1 values in its components and likewise, a vector having 0,1 values in its components will be called a 0-1-vector.

[0009] The processing of binary transformations consist of adding and subtracting components of the input vector. They are implemented in hardware as an electronic Application Specific Integrated Circuit (ASIC), requiring elements such as adders and subtractors. The usage of these components is costly and energy consuming and their construction occupies a precious area. A hardware implementation of binary transformations with a low consumption of these resources is of increasing need in numerous fields of technology.

[0010] There is a widespread usage of U-transformations in various aspects of digital signal processing. It includes a variety of communication technologies such as image processing and wireless communication.

[0011] Currently there is a growing worldwide interest in direct-sequence (DS) code division multiple access (CDMA) spread spectrum communication systems. The IS-95 [TIA/EIA/IS-95-A, “Mobile Station Base Station Compatibility Standard for Dual-Mode Wideband Spread spectrum Cellular System”, Feb. 27, 1996] is one example of the developing DS-CDMA systems.

[0012] In the CDMA transmission technique a multi-user data is send in a composite signal and then multiplied before transmission by a Pseudo-random Noise (PN) code, which is a U-sequence having random noise properties (such as low cross-correlation). The spreading properties makes transmission resistance to noise, including multi-path noise, jamming or detection. A scrambling code, longer than the channeling code, is also applied. This transmission fashion of the second generation (IS-95-B) and third generation (3G) wide band (WB) CDMA standards require the receiver to perform multi-code detection. This is a task of despreading the combined channels simultaneously, each of which was previously spread according to a different channeling code. It is done by application of U-transformations where the spreading codes comprising the transformation matrix are often rows of a Hadamard matrix. This is one of the many examples where effective U-transformation techniques are desired for accomplishing the computational tasks with a low consumption of resources.

[0013] There are several known mechanisms that improve the performance of specific types of linear transformations. A few relevant examples chosen from a very wide range will be mentioned here. Toplitz transformations which perform convolutions and are used as filters in DSP can be done efficiently by the use of the classical Fast Fourier Transform (FFT) algorithm requiring O(n·log₂(n)) addition and multiplication operations, where n is the dimension of the domain space. In comparison the standard, straightforward methods, require O(n²) addition and multiplication. For details see: [James W. Cooley and John W. Tukey, “An algorithm for the machine calculation of complex Fourier series”, Mathematics of computation, 19 (90): 297-301, April 1965.]

[0014] A specific type of U-transformation used in digital signal processing including CDMA technologies is the Walsh-Hadamard Transformation which is represented by a Hadamard matrix. A Hadamard matrix can be defined recursively as follows: $H_1=\left[1\right],H_2=[\begin{array}{cc}1& 1\\ 1& -1\end{array}],$
and for every integer n, a power of 2: $H_{2n}=[\begin{array}{cc}{H}_n& H_n\\ H_n& -H_n\end{array}]$

[0015] A low complexity and energy preserving algorithm for performing this transformation is the Fast Walsh-Hadamard Transform (FWT), which reduces the number of additions/subtractions for nxn Hadamard matrix to n·log₂(n). This provides an optimal saving in these operations. The fundamental ideas underlining this method are similar to those of the FFT

[0016] The U-transformation's aspect is modified by another feature of the invention to accommodate for an efficient method and apparatus for the performance of and toplitz U-transformations. These transformations represents full or partial convolution with a given U-sequence or a complex U-sequence. Wireless communication applications of toplitz U-transformations include initial time-synchronization and the searcher which use convolutions with a real or complex pseudo-random (PN) or gold, U-sequences. A gold sequence is composed by the Z₂ sum of two PN sequences.

[0017] The above binary aspects of the invention are generalized by another aspect of the invention to an efficient method and apparatus for the performance of a linear transformation, represented by an rxn matrix with a relatively small number of different entries. Applications of this advanced aspect of the invention include complex U-transformations and linear transformations represented by an matrix with {0, 1, −1}-entries. This broad preferred embodiment of the invention would be called the generalized-elimination-method (GEM).

[0018] Wide band CDMA and probably other branches of advanced DSP future technologies would benefit from the simultaneous analysis of an incoming signal in different spreading factors. This would give way to a multi-code channel that allows the simultaneous reception of different type of information such as fax, normal phone conversation and internet data without overburdening the network. Another aspect of the present invention is an efficient method and apparatus for these type of linear operations. It comprises modified versions of the U-binary aspect of the invention with an additional processor. This additional processor uses information about the number of additions required by the said U-binary method to discover a configuration that applies the U-binary method in various subsections in global low rate of additions.

[0019] Additional major applications of the invention include wireless multimedia systems personal satellite mobile systems, GPS satellite-based locating systems and more. In the context of mobile communication and other mobile, computational based, systems a reduction in current consumption used for linear processing is essential. Applications of the invention the in the mobile phone technologies can prolong the life of the battery, reduce circuitry and shorten response time.

[0026] There are two new terms that are fundamental for the description of the method of the present invention. The first is that of equivalent vectors. Two non-zero vectors of the same dimension are called equivalent in the text that follows if each one of them is a product of the other. This term may be applied to two rows or two columns of a given matrix. The second term is that of a lead element of a column in a given matrix. The definition used throughout the present invention is the non-zero component of highest index in each column of the said matrix. This definition depends on a predefined columns index-order which is used uniformly in the given matrix. A redefinition of new order results with a redefinition of new lead elements. For example the lead elements of a given matrix may be the bottommost non-zero elements or the uppermost non-zero elements of each column depending on whichever order it seemed convenient to choose as relevant for that purpose.

[0027] The present preferred embodiment of the invention provides an efficient method of performing a 0-1-binary linear transformation. Henceforth it will be called also the “0-1-method”. The following example is an introduction to the 0-1-method and an outline of its main ideas.

[0028] Example: Given a 0-1-binary 4×14 matrix A: $A=[\begin{array}{cccccccccccccc}0& 1& 1& 0& 1& 1& 0& 0& 1& 0& 0& 0& 1& 1\\ 1& 0& 0& 1& 0& 1& 1& 0& 0& 0& 1& 1& 1& 0\\ 0& 0& 1& 1& 1& 1& 0& 0& 0& 0& 1& 0& 1& 1\\ 1& 1& 1& 1& 0& 1& 1& 0& 1& 0& 1& 1& 1& 1\end{array}],$
and an 14-dimensional input vector, $x=[\begin{array}{c}{x}_1\\ x_2\\ ⋮\\ x_{14}\end{array}]$

[0029] Suppose that it is desired to compute the 4-dimensional “output” vector: $y=[\begin{array}{c}{y}_1\\ y_2\\ y_3\\ y_4\end{array}]=[\begin{array}{cccccccccccccc}0& 1& 1& 0& 1& 1& 0& 0& 1& 0& 0& 0& 1& 1\\ 1& 0& 0& 1& 0& 1& 1& 0& 0& 0& 1& 1& 1& 0\\ 0& 0& 1& 1& 1& 1& 0& 0& 0& 0& 1& 0& 1& 1\\ 1& 1& 1& 1& 0& 1& 1& 0& 1& 0& 1& 1& 1& 1\end{array}][\begin{array}{c}{x}_1\\ x_2\\ ⋮\\ x_{14}\end{array}]=A^{*}x.$

[0030] According to a preferred embodiment of the invention the matrix A is first checked for equal lines. Since there are no two lines that are equal, the procedure goes to the next step. Next, the output vector y is expressed as a sum of the columns with coefficients that are the respective input vector coordinates. Hence: $y=x_1[\begin{array}{c}0\\ 1\\ 0\\ 1\end{array}]+x_2[\begin{array}{c}1\\ 0\\ 0\\ 1\end{array}]+x_3[\begin{array}{c}1\\ 0\\ 1\\ 1\end{array}]+x_4[\begin{array}{c}0\\ 1\\ 1\\ 1\end{array}]+x_5[\begin{array}{c}1\\ 0\\ 1\\ 0\end{array}]+x_6[\begin{array}{c}1\\ 1\\ 1\\ 1\end{array}]+x_7[\begin{array}{c}0\\ 1\\ 0\\ 1\end{array}]+x_8[\begin{array}{c}0\\ 0\\ 0\\ 0\end{array}]+x_9[\begin{array}{c}1\\ 0\\ 0\\ 1\end{array}]+x_{10}[\begin{array}{c}0\\ 0\\ 0\\ 0\end{array}]+x_{11}[\begin{array}{c}0\\ 1\\ 1\\ 1\end{array}]+x_{12}[\begin{array}{c}0\\ 1\\ 0\\ 1\end{array}]+x_{13}[\begin{array}{c}1\\ 1\\ 1\\ 1\end{array}]+x_{14}[\begin{array}{c}1\\ 0\\ 1\\ 1\end{array}].$

[0031] At this stage, the zero columns, along with their coefficients would be deleted. The first step done by a preferred embodiment of the invention with respect to the input vector, is to collect and sum coefficients of any recurring non-zero column. Thus with the cost of 6 additions the following reduced vector equation is accomplished: $y=\left(x_1+x_7+x_{12}\right)[\begin{array}{c}0\\ 1\\ 0\\ 1\end{array}]+\left(x_2+x_9\right)[\begin{array}{c}1\\ 0\\ 0\\ 1\end{array}]+\left(x_3+x_{14}\right)[\begin{array}{c}1\\ 0\\ 1\\ 1\end{array}]+\left(x_4+x_{11}\right)[\begin{array}{c}0\\ 1\\ 1\\ 1\end{array}]+x_5[\begin{array}{c}1\\ 0\\ 1\\ 0\end{array}]+\left(x_6+x_{13}\right)[\begin{array}{c}1\\ 1\\ 1\\ 1\end{array}]$

[0032] This expression may be simplified by the following definition:
w₁=x₁+x₇+x₁₂, w₂=x₂+x₉, w₃=x₃+x₁₄, w₄=x₄+x₁₁, w₅=x₅, w₆=x₆+x₁₃,
that implies: $y=[\begin{array}{c}{y}_1\\ y_2\\ y_3\\ y_4\end{array}]=w_1[\begin{array}{c}0\\ 1\\ 0\\ 1\end{array}]+w_2[\begin{array}{c}1\\ 0\\ 0\\ 1\end{array}]+w_3[\begin{array}{c}1\\ 0\\ 1\\ 1\end{array}]+w_4[\begin{array}{c}0\\ 1\\ 1\\ 1\end{array}]+w_5[\begin{array}{c}1\\ 0\\ 1\\ 0\end{array}]+w_6[\begin{array}{c}1\\ 1\\ 1\\ 1\end{array}]$

[0033] This is equivalent to original problem but with a reduced number of columns. However by now this type of reductions is exhausted. To get further gains the vector equation will be split to the following equivalent set of two vector equations: $\begin{array}{c}[\begin{array}{c}{y}_1\\ y_2\end{array}]=w_1[\begin{array}{c}0\\ 1\end{array}]+w_2[\begin{array}{c}1\\ 0\end{array}]+w_3[\begin{array}{c}1\\ 0\end{array}]+w_4[\begin{array}{c}0\\ 1\end{array}]+w_5[\begin{array}{c}1\\ 0\end{array}]+w_6[\begin{array}{c}1\\ 1\end{array}]\\ [\begin{array}{c}{y}_3\\ y_4\end{array}]=w_1[\begin{array}{c}0\\ 1\end{array}]+w_2[\begin{array}{c}0\\ 1\end{array}]+w_3[\begin{array}{c}1\\ 1\end{array}]+w_4[\begin{array}{c}1\\ 1\end{array}]+w_5[\begin{array}{c}1\\ 0\end{array}]+w_6[\begin{array}{c}1\\ 1\end{array}]\end{array}$

[0034] Each of these two equations will be treated separately as in the first step of this preferred embodiment. Thus coefficients of the same nonzero column will be collected and summed. Hence the method arrives at this stage the following set of two vector equations with additional cost of 6 additions: $\begin{array}{c}[\begin{array}{c}{y}_1\\ y_2\end{array}]=\left(w_1+w_4\right)[\begin{array}{c}0\\ 1\end{array}]+\left(w_2+w_3+w_5\right)[\begin{array}{c}1\\ 0\end{array}]+w_6[\begin{array}{c}1\\ 1\end{array}]\\ [\begin{array}{c}{y}_3\\ y_4\end{array}]=\left(w_1+w_2\right)[\begin{array}{c}0\\ 1\end{array}]+\left(w_3+w_4+w_6\right)[\begin{array}{c}1\\ 1\end{array}]+w_5[\begin{array}{c}1\\ 0\end{array}]\end{array}$

[0035] Now it is apparent that only 4 additional additions are required to complete the computation of the output vectory. Hence the desired result was accomplished with the total of 16 additions. It can be readily checked that the conventional prior art method of doing this computational process would require 28 additions. The proceeding description of this preferred embodiment of the invention would reveal a growing relative efficiency of the method as the dimensions of the matrix grows.

[0036] In general the 0-1-binary aspect of the invention is an efficient method and apparatus for the product of a binary 0-1-matrix A of dimensions rxn by an n-dimensional vector x. The matrix is given by: $A=[\begin{array}{cccc}{a}_{11}& a_{12}& \dots & a_{1n}\\ a_{21}& a_{22}& \dots & a_{2n}\\ ⋮& & & \\ a_{\mathrm{r1}}& & & a_{\mathrm{rn}}\end{array}]\mathrm{where}{a}_{\mathrm{ij}}=0,1\mathrm{for}\mathrm{all}1\le i\le r,l\le j\le n.$
and the input vector is given by: $x=[\begin{array}{c}{x}_1\\ x_2\\ ⋮\\ x_n\end{array}]$
The entries of the input vector may be real or complex or belong to any field of scalars (such as Z₂ for example). The goal is to compute the result of the product of the matrix A by the vector x. This result will be denoted by: $y=[\begin{array}{c}{y}_1\\ y_2\\ ⋮\\ y_r\end{array}]=[\begin{array}{cccc}{a}_{11}& a_{12}& \dots & a_{1n}\\ a_{21}& a_{22}& \dots & a_{2n}\\ ⋮& & & \\ a_{\mathrm{r1}}& & & a_{\mathrm{rn}}\end{array}][\begin{array}{c}{x}_1\\ x_2\\ ⋮\\ x_n\end{array}]$

[0037] The procedure that will be described is recursive and the following sequence of steps or part of them will be repeated at each iteration. According to a preferred embodiment of the invention, the first step is a check for equal rows. When possible this step should be done before any processing of input vectors begins, as a preliminary preparation. If it is found that the i-line is equal to the j-line then it can be deducted that y_i is equal to y_j. Therefore one of the two equal lines would be omitted. For the sake of clarity the line having larger index would always be the omitted one. Thus, if j>i then the j-line would be omitted. This initial operation is amended at the final step of the execution of the invention where y_j which is known at this stage (since it is equal to y_i) is inserted back to its appropriate place in the vector y. Omitting of equal lines continues until there are no two line in the matrix A that are equal. In practice this stage is skipped in many occasions. It is performed whenever there is a reasonable likelihood for equal lines. It is always performed when log₂(r)>n since this condition ensures the existence of equal lines.

[0038] To avoid cumbersome notation, the modified matrix resulting from this screening process will have the same name, A, as the original matrix, and the names of the dimensions rxn will also be preserved. In the next stage a summation process is introduced to eliminate equal columns. This procedure will reduce the number of columns in the modified matrix with a minimal cost in additions. First, the matrix by vector product y=A·x is decomposed to the sum of the A-columns multiplied by the respective x-components. Hence: $y=A·x=x_1\left[\begin{array}{c}{a}_{11}\\ a_{21}\\ ⋮\\ a_{r1}\end{array}\right]+x_2\left[\begin{array}{c}{a}_{12}\\ a_{22}\\ ⋮\\ a_{\mathrm{r2}}\end{array}\right]+\dots +x_n\left[\begin{array}{c}{a}_{1n}\\ a_{2n}\\ ⋮\\ a_{rn}\end{array}\right]$

[0039] Each element of this sum consists of a column vector of the matrix A, multiplied by the corresponding scalar coefficient of the vector x. This sum may be written more compactly as: y=A·x=x₁v₁+x₂v₂+ . . . +x_nv_n

[0040] where v_j (for every j) is the j column of A: $v_j=\left[\begin{array}{c}{a}_{1j}\\ a_{2j}\\ ⋮\\ a_{rj}\end{array}\right]$

[0041] According to a preferred embodiment of the invention, zero columns, along with their coefficients are omitted at this stage. Next, identical nonzero columns are grouped together and rearranged where each distinct column becomes a common factor, multiplied by the sum of its corresponding scalar coefficients. Hence, the resulting summation comprises the subsequence of all distinct nonzero columns w₁, . . . , w_m extracted from the original sequence of nonzero column by the omission of repeating columns. Each column w_j is multiplied by a coefficient t_j which is a sum of the corresponding original coefficients of all columns that are equal to this column. It is clear that m≦n, and the gap, n−m, is the number of repetitions in the original sequence v₁, v₂, . . . , v_n. The process described above can be formulated by the following mathematical description: $\begin{array}{c}y=A·x={\sum }_{l\le j\le n}{x}_j{v}_j\\ ={\sum }_{l\le k\le m}{\sum }_{j\mathrm{such}\mathrm{that}:v_j=w_k}{x}_j{v}_j\\ ={\sum }_{l\le k\le m}\left({\sum }_{j\mathrm{such}\mathrm{that}:v_j=w_k}{x}_j\right)w_k.\end{array}$
Now for all 1≦k≦m define: t_k=Σ_{j such that: vj=wk}x_j

[0042] The computational task, so far, is this calculation of the new coefficients t₁, . . . , t_m as sums of the original ones x₁, . . . , x_n. The cost is n−m additions. The product y=A·x is thus given by:
y=A·x=Σ_1≦k≦mt_kw_k

[0043] The management aspect of this computation, of determining the participants in the required sums, may be done once-per-matrix as a preliminary preparation before the arrival of input vectors. To summarize, let B be the rxm matrix whose columns are respectively w₁, . . . , w_m, and let: $t=\left[\begin{array}{c}{t}_1\\ t_2\\ ⋮\\ t_m\end{array}\right]$

[0044] then y=A·x=B·t. Thus the above process reduced the original problem of multiplying the rxn matrix A by the n-vector x to the problem of multiplying the rxm matrix B by the m-vector t. The gain enabled by this is larger when m is smaller.

[0045] The next step is a horizontal split of the matrix B of the former stage to two or more sub-matrix, where lines are kept unbroken. Each sub-matrix will have a reduced number of rows and that will increase the gain of the above column-collection procedure in the next iteration. The lines of the matrix B would be denoted by: u₁, u₂, . . . , u_r. The product under consideration may be then expressed by: $y=B·t=\left[\begin{array}{c}{u}_1·t\\ u_2·t\\ ⋮\\ u_r·t\end{array}\right]$ $u_1·t$

[0046] where each line is multiplied in scalar product by the vector t. In view of this expression the task of computing y=B·t is equivalent to the combined task of computing the r scalar products: u₁·t, u₂·t . . . , u_r·t

[0047] According to a preferred embodiment of the invention this would be done by computing the matrix by vector products: B₁·t and B₂·t where each of the matrix B₁ and B₂ contains a subset of the lines of the matrix B and these two subsets are mutually disjoint and their union comprise of the set of all lines in B. Usually, except for the first iteration, the two sub-matrix would have the same or almost the same number of lines. However depending on the properties of the matrix A in some special cases the split might be into more than two matrix. Such is the case when the matrix A has no special inner order, and its entries may be considered as arbitrarily chosen. Then a preferred embodiment of the invention would usually imply that the first line split that will bring all the split sub matrix to the state where log₂(number of columns)>number of rows. The proceeding iterations would then split the lines to two almost equal halves. The case where the matrix is considered arbitrary is essentially a worst case scenario.

[0048] Another step that might be inserted instead, or before, the above mentioned horizontal split is a vertical split. According to a preferred embodiment of the invention the above mentioned sum:
y=Σ_1≦k≦mt_kw_k

[0049] is split in two:
y=Σ_1≦k≦pt_kw_k+Σ_p+1≦k≦mt_kw_k

[0050] where p is chosen between 1 and m−1. Thus for B₁, the matrix whose set of columns is, w₁, . . . , w_p, and for B₂, the matrix whose set of columns is w_p+1, . . . , w_m it holds that:
y=B₁·t′+B₂·t″

[0051] where the corresponding vectors are: t′=(t₁, . . . , t_p) and t″=(t_p+1, . . . , t_m). Hence by this preferred embodiment of the invention the two lower dimensional products, B₁·t′ and B₂·t″ would be computed separately and in the end the results, which are two r-vectors, are summed together. A preliminary rearrangement of the indexes of the B-columns, w₁, . . . , w_m, may enhance the effectiveness of this step.

[0052] The vertical split would be used less frequently then the others procedures. Its main use is in the case that the number of rows substantially exceeds the number of columns, situation less common in DSP applications. The fundamental drawback of this step is in the need to sum up the results of the two products B₁·t′ and B₂·t″ which consists of an additional set of r scalar additions which has no parallel in the above horizontal split. Like in the above horizontal split, depending on the properties of the matrix A the vertical split might be into more than two matrix.

[0053] Finally each of the above steps are applied in repeated iterations, forming thus a recursive mechanism.

[0054] Next, a bound is presented to the saving enabled by the above method. For an rxn 0-1-matrix A such that r<log₂(n) the number of additions in the worst case, denoted by s*(n, r), is given by the expression:
s*(n, r)=n+s*(r).

[0055] The following table gives the bound to the number of additions for matrix with a small number of rows. $\begin{array}{cc}{s}^{*}\left(2\right)=-1& s^{*}\left(n,2\right)=n-1\\ s^{*}\left(3\right)=2& s^{*}\left(n,3\right)=n+2\\ s^{*}\left(4\right)=7& s^{*}\left(n,4\right)=n+13\\ s^{*}\left(5\right)=22& s^{*}\left(n,5\right)=n+49\end{array}$

[0056] There is the following bound to the worst case:
s*(r)<2^r+2^r/2+2−r.

[0057] The standard (prior art) method requires u(A)−r additions, where u(A) is the number 1'ns in the matrix A. On average (by expectation, when A is arbitrary) u(A)=(n−2)·r/2. Since s*(n , r)/n approaches 1 as n goes to infinity and r is constant (or r≦c·log₂(n) where 1>c>0) this method is asymptotically (for bounded r and unbounded n) optimal.

[0058] When A is an rxn 0-1-matrix and there are no assumptions on the dimensions rxn of the matrix A then the number of additions required by the invention to compute the product A·x is bounded by (1+δ)n·r/log₂(n), where 1>δ>0, and □ goes to zero when both, r and n, go to infinity. In the case that r>n a tighter bound (with respect to this case) exist, which results from the application of the vertical split:
(1+δ)n·r/log₂(r), where 1>δ>0,

[0059] and δ goes to zero when both, r and n, go to infinity.

[0060] To assess the efficiency of this process it should be observed that the present invention increases management operations and reduces additions. However additions are a major part of the complexity and their reduction by the use of the invention has a dominant effect. Moreover, most of the management operations are done once per matrix before the processing of data vectors begins. Thus the suggested method substantially saves power consumption and circuitry. The above 0-1-binary aspect may be particularly efficient when the given matrix has some degree of sparsity. This is often encountered when the application of this embodiment is combined with distributed arithmetic's in the computation of the product of a general real matrix by a vector as described in the real-matrix aspect of the invention.

[0061] In addition this aspect of the invention is applicable in algebraic codes (see: [Shu Lin, Daniel J. Costello, Jr “Error Control Coding Fundamentals and Applications” Prentice-Hall, Inc., Englewood Cliffs, N.J., 1983]) where in the process of coding and decoding a Z₂-matrix is multiplied by a Z₂-vector (or Z_2n-vector). This is true in any situation where a Z₂-matrix is multiplied by a Z_2n-vector. Finally, the above 0-1-binary embodiment and the next U-binary embodiment are easily interchangeable in every field of scalars except for fields of characteristic 2. In each particular case the more efficient embodiment would be chosen.

[0062] A preliminary concept required for the description of the U-binary preferred embodiment of the invention (henceforth called also the “U-method”) is the concept of equivalence of vectors. Two non-zero vectors of the same dimension would be called equivalent if one is a product of the other. In the context of this embodiment, note that two U-vectors are equivalent if they are equal or if one of them is (−1) product of the other. The following preferred embodiment is rather similar in most details to the above one. The main difference is that in the following text elimination is done to equivalent (rows or columns) vectors rather than to equal vector. This speeds the elimination rate and thus enhances the efficiency. This embodiment is introduced through an example, demonstrating the essence of its ideas:

[0063] Example: Consider the product of the following 5×13 U-matrix A by a 13-dimensional input vector x.

[0064] The matrix is given by: $A=\left[\begin{array}{ccccccccccccc}-1& 1& -1& -1& 1& 1& -1& 1& 1& -1& 1& -1& 1\\ 1& -1& -1& 1& 1& -1& 1& -1& -1& 1& -1& -1& 1\\ 1& 1& -1& 1& -1& -1& -1& 1& -1& -1& 1& 1& 1\\ -1& 1& 1& -1& -1& 1& -1& 1& 1& -1& 1& 1& -1\\ -1& 1& -1& -1& 1& 1& -1& 1& 1& -1& 1& 1& 1\end{array}\right]$
and the input vector is given by: $x=\left[\begin{array}{c}{x}_1\\ x_2\\ ⋮\\ x_{13}\end{array}\right]$

[0065] The result of the product is written by: $y=\left[\begin{array}{c}{y}_1\\ y_2\\ y_3\\ y_4\\ y_5\end{array}\right]=A·x$

[0066] The first step in the process is to check for equivalent lines. In practice it is a one time operation done before that arrival of input vectors. A scan discovers one occurrence of equivalent lines in the given matrix, line 2 is equivalent to line 4, in fact line 4 equals to (−1) product line 2. It follows that y₄=−y₂ Therefore it not necessary to compute both y₄ and y₂, hence the computation of y₄ will be omitted. Thus line 4 is deleted from the matrix A. The resulting matrix A′ is given by: $A^{\prime }=[\begin{array}{ccccccccccccc}-1& 1& -1& -1& 1& 1& -1& 1& 1& -1& 1& -1& 1\\ 1& -1& -1& 1& 1& -1& 1& -1& -1& 1& -1& -1& 1\\ 1& 1& -1& 1& -1& -1& -1& 1& -1& -1& 1& 1& 1\\ -1& 1& -1& -1& 1& 1& -1& 1& 1& -1& 1& 1& 1\end{array}]\hspace{1em}$

[0067] The corresponding output vector is given by: $y^{\prime }=\left[\begin{array}{c}{y}_1\\ y_2\\ y_3\\ y_5\end{array}\right]$

[0068] and it holds that: y′=A′·x.

[0069] This is the first reduction. In the next step the product A′·x is decomposed to a sum of the A′-columns multiplied by the respective x-components. Therefore: $\left[\begin{array}{c}{y}_1\\ y_2\\ y_3\\ y_5\end{array}\right]=x_1\left[\begin{array}{c}-1\\ 1\\ 1\\ -1\end{array}\right]+x_2\left[\begin{array}{c}1\\ -1\\ 1\\ 1\end{array}\right]+x_3\left[\begin{array}{c}-1\\ -1\\ -1\\ -1\end{array}\right]+x_4\left[\begin{array}{c}-1\\ 1\\ 1\\ -1\end{array}\right]+x_5\left[\begin{array}{c}1\\ 1\\ -1\\ 1\end{array}\right]+x_6\left[\begin{array}{c}1\\ -1\\ -1\\ 1\end{array}\right]+x_7\left[\begin{array}{c}-1\\ 1\\ -1\\ -1\end{array}\right]+x_8\left[\begin{array}{c}1\\ -1\\ 1\\ 1\end{array}\right]+x_9\left[\begin{array}{c}1\\ -1\\ -1\\ 1\end{array}\right]+x_{10}\left[\begin{array}{c}-1\\ 1\\ -1\\ -1\end{array}\right]+x_{11}\left[\begin{array}{c}1\\ -1\\ 1\\ 1\end{array}\right]+x_{12}\left[\begin{array}{c}-1\\ -1\\ 1\\ 1\end{array}\right]+x_{13}\left[\begin{array}{c}1\\ 1\\ 1\\ 1\end{array}\right]$

[0070] Next, a normalization of each of the column vectors in the above sum is carried out, such that the upper component of each modified vector is 1. Thus the vector and its coefficient are both multiplied by (−1) if the upper component of the vector is (−1). However no modification is done if the upper component of the vector is 1. The following normalized form of the above sum is derived: $\left[\begin{array}{c}{y}_1\\ y_2\\ y_3\\ y_5\end{array}\right]=\left(-x_1\right)\left[\begin{array}{c}1\\ -1\\ -1\\ 1\end{array}\right]+x_2\left[\begin{array}{c}1\\ -1\\ 1\\ 1\end{array}\right]+\left(-x_3\right)\left[\begin{array}{c}1\\ 1\\ 1\\ 1\end{array}\right]+\left(-x_4\right)\left[\begin{array}{c}1\\ -1\\ -1\\ 1\end{array}\right]+x_5\left[\begin{array}{c}1\\ 1\\ -1\\ 1\end{array}\right]+x_6\left[\begin{array}{c}1\\ -1\\ -1\\ 1\end{array}\right]+\left(-x_7\right)\left[\begin{array}{c}1\\ -1\\ 1\\ 1\end{array}\right]+x_8\left[\begin{array}{c}1\\ -1\\ 1\\ 1\end{array}\right]+x_9\left[\begin{array}{c}1\\ -1\\ -1\\ 1\end{array}\right]+\left(-x_{10}\right)\left[\begin{array}{c}1\\ -1\\ 1\\ 1\end{array}\right]+x_{11}\left[\begin{array}{c}1\\ -1\\ 1\\ 1\end{array}\right]+\left(-x_{12}\right)\left[\begin{array}{c}1\\ 1\\ -1\\ -1\end{array}\right]+x_{13}\left[\begin{array}{c}1\\ 1\\ 1\\ 1\end{array}\right]$

[0071] In this normalized sum the upper component of each vector is 1 and the number of different vectors is reduced. The next step is to collect and sum coefficients of the same column. Thus with the cost of 8 additions the following equation is obtained: $\left[\begin{array}{c}{y}_1\\ y_2\\ y_3\\ y_5\end{array}\right]=\left(\left(-x_1\right)+\left(-x_4\right)+x_6+x_9\right)\left[\begin{array}{c}1\\ -1\\ -1\\ 1\end{array}\right]+\left(x_2\left(-x_7\right)+x_8\left(-x_{10}\right)+x_{11}\right)\left[\begin{array}{c}1\\ -1\\ 1\\ 1\end{array}\right]+\left(\left(-x_3\right)+x_{13}\right)\left[\begin{array}{c}1\\ 1\\ 1\\ 1\end{array}\right]++x_5\left[\begin{array}{c}1\\ 1\\ -1\\ 1\end{array}\right]+\left(-x_{12}\right)\left[\begin{array}{c}1\\ 1\\ -1\\ -1\end{array}\right]$

[0072] New coefficient would now be defined:
w₁=(−x₁)+(−x₄)+x₆+x₉, w₂=x₂+(−x₇)+x₈+(−x₁₀)+x₁₁, w₃=−x₃+x₁₃, w₄=x₅, w₅=−x₁₂

[0073] Hence the above equation may be written in the following form: $\left[\begin{array}{c}{y}_1\\ y_2\\ y_3\\ y_5\end{array}\right]=w_1\left[\begin{array}{c}1\\ -1\\ -1\\ 1\end{array}\right]+w_2\left[\begin{array}{c}1\\ -1\\ 1\\ 1\end{array}\right]+w_3\left[\begin{array}{c}1\\ 1\\ 1\\ 1\end{array}\right]+w_4\left[\begin{array}{c}1\\ 1\\ -1\\ 1\end{array}\right]+w_5\left[\begin{array}{c}1\\ 1\\ -1\\ -1\end{array}\right]$

[0074] The coefficients: w₁, w₂, w₃, w₄, w₅ are known to the processor at this stage. In the next stage this vector equation will be split horizontally to the following set of two equation: $\left[\begin{array}{c}{y}_1\\ y_2\end{array}\right]=w_1\left[\begin{array}{c}1\\ -1\end{array}\right]+w_2\left[\begin{array}{c}1\\ -1\end{array}\right]+w_3\left[\begin{array}{c}1\\ 1\end{array}\right]+w_4\left[\begin{array}{c}1\\ 1\end{array}\right]+w_5\left[\begin{array}{c}1\\ 1\end{array}\right]\left[\begin{array}{c}{y}_3\\ y_5\end{array}\right]=w_1\left[\begin{array}{c}-1\\ 1\end{array}\right]+w_2\left[\begin{array}{c}1\\ 1\end{array}\right]+w_3\left[\begin{array}{c}1\\ 1\end{array}\right]+w_4\left[\begin{array}{c}-1\\ 1\end{array}\right]+w_5\left[\begin{array}{c}-1\\ -1\end{array}\right]$

[0075] Now each of these equation will be processed separately in the same manner of the first iteration. The upper equation requires no normalization since it inherited the normal state of the previous equation, and thus normalization is required only for the second equation. Hence the resulting set is: $\left[\begin{array}{c}{y}_1\\ y_2\end{array}\right]=w_1\left[\begin{array}{c}1\\ -1\end{array}\right]+w_2\left[\begin{array}{c}1\\ -1\end{array}\right]+w_3\left[\begin{array}{c}1\\ 1\end{array}\right]+w_4\left[\begin{array}{c}1\\ 1\end{array}\right]+w_5\left[\begin{array}{c}1\\ 1\end{array}\right]\left[\begin{array}{c}{y}_3\\ y_5\end{array}\right]=\left(-w_1\right)\left[\begin{array}{c}1\\ -1\end{array}\right]+w_2\left[\begin{array}{c}1\\ 1\end{array}\right]+w_3\left[\begin{array}{c}1\\ 1\end{array}\right]+\left(-w_4\right)\left[\begin{array}{c}1\\ -1\end{array}\right]+\left(-w_5\right)\left[\begin{array}{c}1\\ 1\end{array}\right]$

[0076] In the next step the coefficients of the same vector are collected and summed. Thus with additional 6 additions the outcome is: $\left[\begin{array}{c}{y}_1\\ y_2\end{array}\right]=\left(w_1+w_2\right)\left[\begin{array}{c}1\\ -1\end{array}\right]+\left(w_3+w_4+w_5\right)\left[\begin{array}{c}1\\ 1\end{array}\right]\left[\begin{array}{c}{y}_3\\ y_5\end{array}\right]=\left(-w_1-w_4\right)\left[\begin{array}{c}1\\ -1\end{array}\right]+\left(w_2+w_3+w_5\right)\left[\begin{array}{c}1\\ 1\end{array}\right]$

[0077] Clearly, the vector y′ is found with 4 more additions. To obtain the original output vector y it is only necessary to recall now that y₄=−y₂. Thus the total of 18 additions was required for this process. Observe that conventional prior art methods would require the total of 60 additions to compute the output vector.

[0078] The U-binary preferred embodiment of the invention is an efficient method for the product of a rxm U-matrix A by an n-dimensional input vector x. It usually provides more gain than the 0-1-preferred embodiment and has more applications.

[0079] The matrix A is given by: $A=\left[\begin{array}{cccc}{a}_{11}& a_{12}& \dots & a_{1n}\\ a_{21}& a_{22}& \dots & a_{2n}\\ ⋮& & & \\ a_{\mathrm{r1}}& & & a_{rn}\end{array}\right]\mathrm{where}{a}_{\mathrm{ij}}=\pm 1\mathrm{for}\mathrm{all}1\le i\le r,1\le j\le n.$
and the input vector is written by: $x=\left[\begin{array}{c}{x}_1\\ x_2\\ ⋮\\ x_n\end{array}\right]$

[0080] The entries of the input vector may be real or complex or belong to any field of scalars with characteristic larger then 2. The goal is to compute the result of the product:
y=A·x.

[0081] The first step is a modification of the given matrix by the elimination of equivalent lines, a step which may be part of preliminary preparations. If it is found that the i-line is equivalent to the j-line then it can be deducted that y_i is equal to ±y_j. Therefore a preferred embodiment of the first step of the invention determines that one of two equivalent lines would be omitted. For the sake of clarity the policy would be that the line having larger index would always be the omitted one. Thus, if it is supposed that j>i then the j-line would be omitted. This initial operation is reversed at the final step of the process where y_j which is known at this stage is put back to its place in the vector y. This elimination process continues until there are no two line in the modified matrix that are equivalent.

[0082] This stage is performed whenever there is a practical probability of equivalent lines. This is often the case in multi-product (another aspect of the present invention) applications of the U-method. This stage is always performed when log₂(r)≧n since this condition ensures the existence of equivalent lines. However there are other conditions that ensures the existence of equivalent lines and should be taken into consideration. This for example, may be the case in sub-matrix of the Hadamard matrix. To avoid clumsy notation, the resulting modified matrix will have the same name, A, as the original matrix, and the names of the dimensions rxn will also be preserved.

[0083] The next step is the elimination of equivalent columns. This will reduce the horizontal dimension (i.e. the number of columns) of the modified matrix with minimal cost in additions. All the management related to this step is made, as in the 0-1-aspect, one time per each matrix usually as preliminary preparation prior to the arrival of data vectors. First, the product y=A·x is expressed as a sum of the A-columns multiplied by the corresponding x-component. $\mathrm{Let}{v}_j\left(\mathrm{for}\mathrm{every}j\right)\mathrm{be}\mathrm{the}j\mathrm{column}\mathrm{of}A\text{:}{v}_j=\left[\begin{array}{c}{a}_{1j}\\ a_{2j}\\ ⋮\\ a_{rj}\end{array}\right]$ $\mathrm{Then}\text{:}A·x=x_1{v}_1+x_2{v}_2+\dots +x_n{v}_n$

[0084] Next, the upper element of each column vector of the matrix A is examined and normalized to +1 value, if it is not already +1. Hence, when a_1j=+1 then no normalization is required whereas if a_1j=−1 then normalization is takes place and the corresponding j-column vector is multiplied by −1, as well as its corresponding coefficient x_j. A new representation of the above sum in is thus obtained, where the upper entry of each vector being equal to +1. In this representation equivalent columns are always equal.

[0085] Identical columns are then grouped together, as in the above 0-1-embodiment, and rearranged by taking each column as a common factor, multiplied by the sum of its corresponding scalar coefficients. Hence, the resulting summation comprises the subsequence of all distinct normalized column vectors w₁, . . . , w_m (having no repetitions) extracted from the sequence of normalized column vectors by screening out repeating normalized columns. Each distinct normalized column w_j is multiplied by a coefficient t_j which is a sum of the corresponding normalized coefficients of all normalized columns that are equal to this column. It is clear that m≦n, and the difference, n−m, is the number of repetitions in the original sequence of normalized columns: a₁₁v₁, a₁₂v₂, . . . , a_1nv_n.

[0086] Mathematically the process is: $\begin{array}{c}A·x={\sum }_{i\le j\le n}{x}_j{v}_j\\ ={\sum }_{l\le k\le m}{\sum }_{j\mathrm{such}\mathrm{that}{a}_{1j}{v}_j=w_k}\left(x_j{a}_{1j}\right)a_{1j}{v}_j\\ ={\sum }_{l\le k\le m}{\sum }_{j\mathrm{such}\mathrm{that}{a}_{1j}{v}_j=w_k}{a}_{1j}{x}_j)w_k\end{array}$
For all 1≦k≦m define: t_k=Σ_{j such that: vj=wk}a_1jx_j

[0087] The main computational task involved in this part of the invention is this calculation of the new coefficients t₁, . . . , t_m as sums of the normalized original ones. The cost in additions is n−m. The product A·x is thus given by:
A·x=Σ_1≦k≦mt_kw_k

[0088] The gain by the columns elimination process depends on the structure of the original matrix A. It is significant in some of the matrix that are commonly used in coding and decoding signal vectors in wireless communication, such as certain types of submatrix of the Hadamard or the cyclic PN matrix. It is substantial also when r, the number of lines in the matrix A, is small relative to the number of rows n. In particular when r≦log(n), in such case m−n≧n−2^r−1>0. These observations are largely true also for 0-1-matrix.

[0089] The remaining part of this preferred embodiment of the invention, horizontal and vertical splitting, iterations, is equivalent to its 0-1-counterpart.

[0090] To view the saving enabled by the use of the invention note first that additions are the main part of the complexity. For a rxn U-matrix A such that r≦log₂(n) the number of additions in the worst case, denoted by s(n, r), is given by:
s(n, r)=n+s(r)

[0091] where: $\begin{array}{cc}s\left(1\right)=-1& s\left(n,1\right)=n-1\\ s\left(2\right)=0& s\left(n,2\right)=n\\ s\left(3\right)=3& s\left(n,3\right)=n+3\\ s\left(4\right)=8& s\left(n,4\right)=n+8\\ s\left(5\right)=19& s\left(n,5\right)=n+19\\ s\left(6\right)=38& s\left(n,6\right)=n+38\\ s\left(7\right)=75& s\left(n,7\right)=n+75\\ s\left(8\right)=144.& s\left(n,8\right)=n+144\\ s\left(9\right)=283& s\left(n,9\right)=n+283\end{array}$

[0092] The following bound is always valid:
s(r)<2^r−1+2^r/2+1−r

[0093] The prior art conventional method requires (n−1)·r additions. Since s(n , r)/n approaches 1 as n goes to infinity and r is constant this method is asymptotically optimal. The more complex multi-product embodiment of the invention that will be described later requires a precise bound to the worst case number of additions. This will be enabled by the following regression formula.
For even r: s(r)=2^r−1+2s(r/2)
For odd r: s(r)=2^r−1+s((r+1)/2)+s((r−1)/2)

[0094] When A is an rxn U-matrix and there are no restrictions on the dimensions rxn of the matrix A then the number of additions required by the invention to compute the product A·x in the worst case is always bounded by: (1+δ)n·r/log₂(n), where 1>δ>0, and δ goes to zero when both, r and n, go to infinity. In the case that r>n a tighter bound (with respect to this case) exist, which results from the application of the vertical split:
(1+δ)n·r/log₂(r), where 1>δ>0,

[0095] and δ goes to zero when both, r and n, go to infinity.

[0096] However, if there is a specific type of structure in the matrix A then the number of additions required by the preferred embodiment of the present invention to compute the product A·x may drop drastically. The most general conditions for it are beyond the scope of the current text but some examples would be mentioned. However in the cases where A is nxn Hadamard or cyclic pseudo-random (PN) matrix then only n·log₂(n), additions, and a memory of n scalars, would be required, which is optimal in this respect. This remark holds also for the 0-1-matrix.

[0097] There are several technologies that will benefit from implementation of the preferred embodiment of the invention, described above. One such technology is image processing which encompass several procedures which include the product of a U-matrix by a vector. In wireless communication CDMA, IS-95 and in the more advanced third generation wide band CDMA, there are several processes which employ the product of a U-matrix by a vector. These processes will be done with less energy consumption, circuitry and sometimes also running time by the use of the invention.

[0098] In the context of multi-code in the IS-95-B, 8 lines of from the Hadamard-64 comprise a U-matrix which is multiplied by a vector whose entries are samples of a signal. Another application is in neighbor detection which done by a despreader. Here too there is a product of a matrix composed of few Hadamard lines by a data vector. Another application is the searcher. It searches for high correlation of sequences by the computation of their mutual scalar product. The correlator sequences are extracted from pseudo random (PN) sequences, which are U-sequences, and their scalar products by a data vector is the required computation. Initial inquisition is one instance of a searcher.

[0099] The above binary aspects of the invention are characterized by iterations of the following processes: zero lines and equivalent lines (meaning that one is a scalar product of the other) are omitted; zero columns are omitted along with the scalar components of the input vector associated with them; equivalent columns are grouped and summed together and the matrix is split horizontally or vertically after these two features are exhausted. According to a preferred embodiment of the invention this iterative sequence of steps may be applied to any product of matrix by vector, in any field of scalars. This broader preferred embodiment of the invention would be called the generalized-elimination-method (GEM).

[0100] The summation of equivalent columns is fundamentally a repetition of the following process. Let v₁, v₂, . . . , v_n be the columns of the transformation matrix A and x=(x₁, x₂, . . . , x_n) be the input vector and the goal is to compute: A·x. Suppose that it holds after an appropriate rearrangement of the indexes that each of the columns v_k+1, . . . , v_n (for some 2≦k<n) is a scalar product of the k-column, that is for k<j≦n: v_j=z_jv_k. Then the n-dimensional vector x is replaced by the reduced k-dimensional vector:
x′=(x₁, x₂, . . . , x_k−1, x′_k) where x′_k=x_k+x_k+1·z_k+1+ . . . +x_n·z_n
and the rxn matrix is replaced by the reduced rxk matrix A′ whose columns are v₁, v₂, . . . , v_k. It then holds that that: A′·x′=A·x. According to a preferred embodiment of the invention this process, including, if necessary a change of indexes, is repeated until no two columns are equivalent. Indeed this is process is simply a generalization of the process of normalization taken place in the U-matrix embodiment of the invention. In practice all the above equivalent-columns reductions may be done simultaneously. When this stage is done it would be considered a first iteration of the whole process. Then the matrix is split horizontally and in each split the above column elimination repeats in a recursive manner as was done in the above embodiments.

[0101] As is demonstrated by the U-embodiment and by next example an efficient method to eliminate equivalent columns is by first dividing each column by the upper most component and accordingly multiplying the corresponding coefficient by the same uppermost component. It results with having 1 in the uppermost component of the each modified column. However, sometimes in applications of the GEM the uppermost component of a column in the transformation matrix is zero making this division impossible. In such cases the simple solution is to divide each nonzero column by its uppermost non zero component and accordingly multiply the corresponding coefficient by the same uppermost non zero component. The results is that there is 1 in the uppermost non zero component of the each modified column. This have the desirable consequence that two columns are equivalent in the modified matrix if and only if they are equal.

[0102] To allude to cases where this preferred embodiment of the invention enhances the efficiency, consider a matrix having its entries in a relatively small finite set S. In practice this set S maybe a finite field a finite subgroup of the multiplication group of a field or a finite subset of a field closed under multiplication, and in greater generality any finite subset of a field. It includes the binary cases discussed above where S={0,1}, or S={1,−1} and other very common situations where S={0, 1, −1} or S={1,−1j,−j} or S={0, 1, −1j,−j}. The gain decreases with the size of S and the general rule holds that the GEM reduces the number of additions by a factor of log_|s|(n), where n is the number of columns in the given transformation matrix. When applicable, the GEM should also be compared for efficiency with the complex and general embodiments that will later be described.

[0103] To illustrate the way this method works it would be demonstrated for a matrix whose entries are from the set: U₁=_def={1, −1, j, −j} called U₁-matrix. Such type of matrix appear often in practice. However, it must be emphasized again that the GEM is not limited to any specific type of matrix. The number of additions is bounded by C=n+4^r−1+o(4^r−1) for the product of rxn U₁-matrix by a vector.
Example: Consider the product of the following 3×15 U₁-matrix A by a 15-dimensional complex input vector x. The matrix is given by: $A=[\hspace{1em}\begin{array}{ccccccccccccccc}1& -j& j& -1& 1& -j& -1& j& -1& j& -1& 1& -j& 1& j\\ -1& j& -1& j& 1& j& 1& 1& j& -j& -j& -j& -j& -1& -j\\ j& 1& -1& j& j& j& 1& -1& 1& -1& -1& -j& 1& j& -1\end{array}\hspace{1em}]$
and the input vector is given by: $x=\left[\begin{array}{c}{x}_1\\ x_2\\ ⋮\\ x_{15}\end{array}\right]$
The result of the product is written by: $y=\left[\begin{array}{c}{y}_1\\ y_2\\ y_3\end{array}\right]=A·x$

[0104] All the additions that are done in this example are complex additions. The first step is a check for equivalent lines. No equivalent lines are found. In the next step the product A·x is decomposed to a sum of the A-columns multiplied by the respective x-components. $\begin{array}{c}\left[\begin{array}{c}{y}_1\\ y_2\\ y_3\end{array}\right]=x_1\left[\begin{array}{c}1\\ -1\\ j\end{array}\right]+x_2\left[\begin{array}{c}-j\\ j\\ 1\end{array}\right]+x_3\left[\begin{array}{c}j\\ -1\\ -1\end{array}\right]+x_4\left[\begin{array}{c}-1\\ j\\ j\end{array}\right]+x_5\left[\begin{array}{c}1\\ 1\\ j\end{array}\right]+\\ x_6\left[\begin{array}{c}-j\\ j\\ j\end{array}\right]+x_7\left[\begin{array}{c}-1\\ 1\\ 1\end{array}\right]+x_8\left[\begin{array}{c}j\\ 1\\ -1\end{array}\right]+x_9\left[\begin{array}{c}-1\\ j\\ 1\end{array}\right]+x_{10}\left[\begin{array}{c}j\\ -j\\ -1\end{array}\right]+\\ x_{11}\left[\begin{array}{c}-1\\ -j\\ -1\end{array}\right]+x_{12}\left[\begin{array}{c}1\\ -j\\ -j\end{array}\right]+x_{13}\left[\begin{array}{c}-j\\ -j\\ 1\end{array}\right]+x_{14}\left[\begin{array}{c}1\\ -1\\ j\end{array}\right]+x_{15}\left[\begin{array}{c}j\\ -j\\ -1\end{array}\right]\end{array}$

[0105] Next, a normalization of each of the column vectors in the above sum takes place. It is done by multiplying each vector by the inverse of its upper component and accordingly multiplying each coefficient by the (same) upper component of the corresponding vector. Hence the upper component of each modified vector is 1. No modification is needed if the upper component of the vector is already 1. The following normalized form of the above sum is derived: $\begin{array}{c}\left[\begin{array}{c}{y}_1\\ y_2\\ y_3\end{array}\right]=x_1\left[\begin{array}{c}1\\ -1\\ j\end{array}\right]+\left(-j\right)·x_2\left[\begin{array}{c}1\\ -1\\ j\end{array}\right]+j·x_3\left[\begin{array}{c}1\\ j\\ j\end{array}\right]+\left(-1\right)x_4\left[\begin{array}{c}1\\ -j\\ -j\end{array}\right]+\\ x_5\left[\begin{array}{c}1\\ 1\\ j\end{array}\right]+\left(-j\right)x_6\left[\begin{array}{c}1\\ -1\\ -1\end{array}\right]+\left(-1\right)x_7\left[\begin{array}{c}1\\ -1\\ -1\end{array}\right]+j·x_8\left[\begin{array}{c}1\\ -j\\ j\end{array}\right]+\\ \left(-1\right)x_9\left[\begin{array}{c}1\\ -j\\ -1\end{array}\right]+j·x_{10}\left[\begin{array}{c}1\\ -1\\ j\end{array}\right]+\left(-1\right)x_{11}\left[\begin{array}{c}1\\ j\\ 1\end{array}\right]+x_{12}\left[\begin{array}{c}1\\ -j\\ -j\end{array}\right]+\\ \left(-j\right)x_{13}\left[\begin{array}{c}1\\ 1\\ j\end{array}\right]+x_{14}\left[\begin{array}{c}1\\ -1\\ j\end{array}\right]+j·x_{15}\left[\begin{array}{c}1\\ -1\\ j\end{array}\right]\end{array}$
In this normalized sum the upper component of each vector is 1 and the number of different vectors is thus reduced substantially when (in the general setting) the number of columns n is sufficiently large relative to the number of rows r (the requirement is: n>4^r−1). The next step is to collect and sum coefficients of the same column. Thus with the cost of 7 additions the following reduction is obtained: $\begin{array}{c}\left[\begin{array}{c}{y}_1\\ y_2\\ y_3\end{array}\right]=\left(x_1+\left(-j\right)·x_2+j·x_{10}+x_{14}+j·x_{15}\right)\left[\begin{array}{c}1\\ -1\\ j\end{array}\right]+j·x_3\left[\begin{array}{c}1\\ j\\ j\end{array}\right]+\\ \left(\left(-1\right)x_4+x_{12}\right)\left[\begin{array}{c}1\\ -j\\ -j\end{array}\right]+\left(x_5+\left(-j\right)x_{13}\right)\left[\begin{array}{c}1\\ 1\\ j\end{array}\right]+\\ \left(\left(-j\right)x_6+\left(-1\right)x_7\left[\begin{array}{c}1\\ -1\\ -1\end{array}\right]\right)+j·x_8\left[\begin{array}{c}1\\ -j\\ j\end{array}\right]+\left(-1\right)x_9\left[\begin{array}{c}1\\ -j\\ -1\end{array}\right]+\\ \left(-1\right)x_{11}\left[\begin{array}{c}1\\ j\\ 1\end{array}\right]\end{array}$

[0106] New coefficient would now be defined:
w₁=x₁+(−j)·x₂+j·x₁₀+x₁₄+j·x₁₅, w₂=j·x₃
w₃=(−1)x₄+x₁₂, w₄=x₅+(−j)x₁₃, w₅=(−j)x₆+(−1)x₇.
w₆=j·x₈, w₇=(−1)x₉, w₈=(−1)x₁₁

[0107] Hence the above equation may be written in the following form: $\begin{array}{c}\left[\begin{array}{c}{y}_1\\ y_2\\ y_3\end{array}\right]=w_1\left[\begin{array}{c}1\\ -1\\ j\end{array}\right]+w_2\left[\begin{array}{c}1\\ j\\ j\end{array}\right]+w_3\left[\begin{array}{c}1\\ -j\\ -j\end{array}\right]+w_4\left[\begin{array}{c}1\\ 1\\ j\end{array}\right]+w_5\left[\begin{array}{c}1\\ -1\\ -1\end{array}\right]+\\ w_6\left[\begin{array}{c}1\\ -j\\ j\end{array}\right]+w_7\left[\begin{array}{c}1\\ -j\\ -1\end{array}\right]+w_8\left[\begin{array}{c}1\\ j\\ 1\end{array}\right]\end{array}$
The coefficients: w₁, . . . , w₈ are known to the processor at this stage. Next, this vector equation will be split horizontally to the following equivalent set of two equation: $\begin{array}{c}\left[\begin{array}{c}{y}_1\\ y_2\end{array}\right]=w_1\left[\begin{array}{c}1\\ -1\end{array}\right]+w_2\left[\begin{array}{c}1\\ j\end{array}\right]+w_3\left[\begin{array}{c}1\\ -j\end{array}\right]+w_4\left[\begin{array}{c}1\\ 1\end{array}\right]+w_5\left[\begin{array}{c}1\\ -1\end{array}\right]+\\ w_6\left[\begin{array}{c}1\\ -j\end{array}\right]+w_7\left[\begin{array}{c}1\\ -j\end{array}\right]+w_8\left[\begin{array}{c}1\\ j\end{array}\right]\end{array}$  [y₃]=w₁[j]+w₂[j]+w₃[−j]+w₄[j]+w₅[−1]+w₆[j]+w₇[−1]+w₈[1]