Abstract:
A system and apparatus for encoding a set of input vector components by initiating a sequential search through a codebook memory to put out a series of associated error code vectors which can be compared in sequence over a period of time in order to select the minimum error code vector (best fit). A clocking-sequencing means enables an output latch to hold (after termination of the sequence period) the index number which represents the particular error code vector presently having the minimum distortion. Each new set of input vector components will be sequenced to search for the minimum error code vector (and index) for that particular set of input vector components.

Description:
FIELD OF THE INVENTION 
     This disclosure relates to the field of data compression whereby vectors can be quantized using an error codebook to select a code vector which best matches an input vector. 
     BACKGROUND OF THE INVENTION 
     Presently there is an increasing trend toward the development of data transmission networks which can incorporate digital voice, data, and image information on the same network. These are generally called ISDN or Integrated Services Digital Networks. Since these networks have a limited band width for transmission of information, the available band width must be used as efficiently as possible. For many years, the analysis, modeling, and coding of information to reduce the overall bit rate has been actively studied. In order to achieve the best results different techniques are applied to different types of information. &#34;Vector quantization&#34;, is one specific technique that has applications in both voice compression and image compression. Image data is particularly challenging to compress because of the large amount of digital information required to accommodate the human eye. Another variation of vector quantization is often referred to as color/spatial quantization and has been developed to efficiently encode such images as color maps. Vector quantization is not limited to any specific type of data but has applications wherever there is redundant information that can be removed with a lossy compressor. 
     The primary goal of network services is to allow distributed processing and exchange of information in an environment in which central locations are responsible for maintaining data bases. Networks, such as the telephone system, have been developed for voice transmission. Other types of computer networks operate with digital data and with file transfers. Thus the need for special purpose networks and transmission links will continue to be a rapidly developing subject. The growing trend is to provide and operate integrated networks which carry digital voice data, information data, and image data. These integrated digital networks will provide the basis for efficiently exchanging information and maintaining data bases. Regardless of the size of the network or the type of the information that is being processed, there will always be a need for efficient storage and transmission. Thus the compression of voice data, information data, and image data will be a key technology for ISDN networks. 
     Many techniques have been developed for the compression of digital, voice, data and images. Each method takes advantage of specific characteristics of the data. Also consideration must be given to the purpose or final use of the data. For example, voice information and image information do not require perfect replication so long as the introduced distortion is not misleading or disturbing to the listener or observer. On the other hand, computer files that even have a single error are possibly no longer of adequate use. When a compression algorithm is able to restore the encoded data to its original form, with no degradation, the algorithm is referred to as a &#34;lossless&#34; data compression technique. Other algorithms that introduce an acceptable amount of distortion are referred to as &#34;lossy&#34; data compression techniques. Thus the requirements of the user will dictate which approach is best suited for compression of the data. 
     When a compression algorithm is chosen, the advantages of reduced storage and transmission charges must be compared to the cost and complexity of the implementation. Today&#39;s hardware operates at higher speeds, allows greater complexity, and is considerably less expensive than ever before. Thus these hardware advances allow complex algorithms to process data before and after storage and transmission. Special purpose hardware also allows algorithms to be directly implemented at reduced costs. Regardless of the approach, compression techniques are continually being reevaluated. However, many algorithms that were not feasible in the past are now realizable. 
     LOSSY COMPRESSION: Much of the data that is transmitted on an information channel is for use by the human sensory system. Minor alterations or infrequent errors to this data is undetectable or tolerable to human senses. Many compression techniques capitalize on this phenomena. When a technique is able to reduce the data rate and bandwidth required to send the information by controlling the distortion without intolerable changes to the data, it is referred to as lossy compression. Vector quantization is a lossy technique for reducing the amount of information to be transmitted or stored. This is accomplished by removing information that is perceived as useless in the particular application being considered. Presently a considerable amount of anticipation exists because of the gains that are being realized in the area of image compression by using vector quantization. A description of vector quantization and examples as applied to image compression follow. 
     VECTOR QUANTIZATION: Vector quantization is a technique for mapping vectors from a given vector space into a reduced set of vectors within the original vector space or some other representative vector space. The reduced set of vectors, along with the associated mapping, is chosen to minimize error according to some distortion measure. This representative set of vectors is referred to as a codebook and is stored in a memory table. Efficient transmission of vector quantized data occurs by sending a codebook index location from the memory table, rather than sending the vector itself. The computation required to compute the distortions, thereby finding the codebook entry of minimum distortion, has limited the availability of the technique. Advances in hardware allowing cost-efficient implementations of vector quantization have generated renewed systems of implementation during the last few years. 
     An optimal vector quantizer is designed around a probability distribution, placing the codevectors in the space according to vector probabilities. Vector probability distributions vary with different data. The LBG algorithm (discussed hereinbelow) uses either a known probability distribution, or trains the codevectors on a select set of training vectors. If the probability distribution is known, the codevectors are placed in the N dimensional vector space according to the probability distribution. Areas of high probability contain a larger population of codevectors; low probability areas contain a sparse population. If the probability distribution is not known, the codevectors are distributed according to a select set of training vectors. Iteratively selecting codevectors to minimize distortion results in a locally optimal set of codevectors. The algorithm guarantees convergence of a local minimum distortion, but not convergence to an absolute minimum for all vectors. 
     The vector quantization encoding process searches the representative codevectors and replaces the input vector from the data source with an index. The index represents the codebook vector of minimum distance from the incoming vector. Distance between vector and codevector is proportional to the amount of degradation that will occur from vector quantization. Distance is most often measured by using a squared error criterion but many others are discussed in the literature. 
     Recent developments in vector quantization have shown the technique to be useful for voice and for image compression. Because of advances in hardware which allow cost-efficient implementations, vector quantization methods have been expanded in development. 
     A fundamental result of rate distortion theory is that better overall compression performance can be achieved when encoding a vector (group of scalars) than when encoding the scalars individually. This development has been presented in an article by R. Gray entitled &#34;Vector Quantization&#34; in the IEEE ASSP magazine, of April 1984. Vector quantization takes advantage of this theory by compressing groups of scalars, and treating each scalar as a vector coefficient. As an image compression scheme, vector quantization has both theoretically and experimentally outperformed methods of image compression using scalar quantization. 
     Methods of compression attempt to remove redundancies, while causing minimal distortion. Vector quantization uses four properties of vector parameters for redundancy removal, namely: correlation; nonlinear dependency; probability density function; shape and vector dimension. Scalar quantization takes advantage of correlation and probability density function shape only. By using the properties of nonlinear dependencies and vector dimensionality, vector quantization is able to outperform scalar quantization even when compressing totally uncorrelated data and an optimal vector quantizer is designed around a probability distribution, placing the &#34;code vectors&#34; in the space according to vector probabilities. Vector probability distributions vary with different data. For example, in an article in the IEEE Transactions on Communications, January, 1980, entitled &#34;An Algorithm for Vector Quantizer Design&#34; by Y. Linde, R. Gray, and A. Buzo, there was developed an algorithm designated as the &#34;LBG&#34; algorithm which uses either a known probability distribution or trains the code vectors on a select set of training vectors. If the probability distribution is known, the code vectors are placed in the N dimensional vector space according to the probability distribution. Areas of high probability contain a larger population of code vectors; but low probability areas contain a sparse population. If the probability distribution is not known, the code vectors are distributed according to a select set of &#34;training vectors&#34;. Iteratively selecting code vectors, that minimize distortion caused by encoding the training vectors, results in a &#34;locally optimal set&#34; of code vectors. The algorithm guarantees convergence of a local minimum distortion, but not convergence to an absolute minimum for all vectors of the training sequence. 
     The &#34;vector quantization encoding process&#34; operates to match a representative code vector with each input vector. The code vector that is the minimum distance from the incoming vector, is chosen as the representative code vector. The distance between the incoming vector and the code vector is proportional to the amount of degradation that will occur from vector quantization. This distance is measured by finding the Euclidian distance between the incoming vectors and code vectors. The Euclidian distances are then measured using a means squared error distortion formula as follows: ##EQU1## 
     Where x i  is the image vector coefficient and Y i  is the code vector coefficient. By minimizing the term d(x,y) over all of the code vectors, this will cause the selection of the &#34;closest&#34; code vector, and thus gives the best possible match between the incoming vector and the code vector. 
     By representing this larger set of incoming vectors with a smaller subset of code vectors, enables a reduction in the amount of information required. The rate of compression realized is a function of the vector dimension X, r  the code vector subset size L,(2 k ) and the scalar size k(2 8 ). 
     SUMMARY OF THE INVENTION 
     The present invention involves the use of a predefined codebook which has 2 k  vectors of dimensions &#34;r&#34; where 2 k  represents the number of tree branches in the codebook. The system features provision for finding of the &#34;best fit&#34; vector of dimension &#34;r&#34; from the predefined codebook. &#34;Best fit&#34; represents the vector which provides the least distortion, where the measure of distortion is predetermined by the user and is independent of the hardware. By making a calculation of the error deviation (distortion) between each input vector and each codebook vector, it is possible to find the closest or best fit codebook vector which matches the input vector. 
     It is necessary in this situation to calculate the differences or &#34;distortion&#34; between each of the input vectors under consideration and each of the residing codebook vectors in memory in order to determine which codebook vector most closely matches any given input vector. 
     The present system eliminates the need to perform these calculations in expensive and complex hardware; rather instead, all of the component error terms for all of the possible input vector components are precalculated and stored in a memory arrangement. 
     The memory arrangement for the error codebook uses an architecture by which a sequence operated by a clock-counter outputs the code vector component according to the index of the sequencer. 
     The memory arrangement provides for &#34;r&#34; memories where r is the number of input vector components and each memory simultaneously provides an error code to a summation means, which error code (for that set of input vector components) is latched into a first input latch means. A counter means sequences a search of each memory to provide another error code to the first input latch means. 
     Then a comparison-selection means operates to compare each subsequent output error code against the previous error code so that the first input latch means will retain the lower value of any two compared error codes. A second output latch means will hold the Index number of that error code which was the smallest (minimum) value of the sequenced set of comparisons. 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS 
     FIG. 1 is a block diagram of the basic elements of the best fit selection system for encoding input vectors using the error codebook to provide an output code symbol or index for transmission on a data link. 
     FIG. 2A shows a simple illustration of a tree search codebook where each node represents a different level of refinement in a digital sense; FIG. 2B illustrates a multiple level codebook tree structure indicating how a search is made through each level to find the codebook vector block which most closely matches the input vector block. 
    
    
     DESCRIPTION OF PREFERRED EMBODIMENT 
     As shown in FIG. 1, there is presented a diagram of the system whereby a series of vector components P 1 , P 2 , . . . P r  (previously quantized to &#34;q&#34; bits of scalar information) present a series of input information into a codebook memory system which permits a comparison selection means to select the best fit code index 80 which can be transmitted on a data link to a decoder which will replace the index with a vector from a codebook. 
     Here is seen a plurality of memory storage devices which go to form the codebook which provides code vectors whereby each code vector is designated with information which shows how much distortion or error deviation occurs between the input vector component information and the output code vector from each memory. 
     For example, pixel information of 8 bits may be fed at input P 1  ; likewise another pixel information data of 8 bits may be fed into input P 2  and so on until final pixel information of 8 bits may be fed into the input P r . 
     Each vector component input P 1 , P 2 , . . . P r  is fed to its own individual memory codebook unit where, as seen in FIG. 1, each codebook memory unit has a length of 2 q+k  and a memory width of 2 m  bits. 
     Here the symbol &#34;q&#34; represents the number of input bits of information for each of the input vector lines. For example, if 8 bits of information are provided on the input line P 1 , then the value of q is equal to 8. 
     The symbol &#34;k&#34; represents a number for denoting memory size since memories are manufactured on number sizes based on &#34;2&#34;. 
     The symbol &#34;m&#34; represents the number of output bits which are released from the memories. Thus, if the code vector output provides a signal of 4 bits then m is equal to 4. And thus, similarly the 2 m  memory width would be equal to 2 4  which would be 16 ERROR DEVIATIONS. 
     The size of the codebook would be represented by 2 k . Thus if k is equal to 4, then 2 4  would be equal to 16 and the codebook would provide a tree of 16 branches. To put it another way, there would be 16 separate branchings in the tree for searching to provide a selected codebook vector. Codebook sizes that are greater than 2 k-1  and less than 2 k  are considered special cases of codebook size 2 k  where some vector components would be repeated or nullified. 
     Situated within each memory is a series of data involving precalculated error functions (deviations). Thus for each code vector in the memory which is selected by the input component, there will be provided an output which places a value on the amount of deviation between the input vector component and the selected code vector. This &#34;error deviation&#34; is designated (for input vector component P 1 ) as: 
     
         (p.sub.1 -x.sub.ln).sup.a. 
    
     Likewise the &#34;error deviation&#34; between input component P r  and the code vector selected from the memory 30 r  will be seen to be shown as: 
     
         (P.sub.r -x.sub.rn).sup.a. 
    
     Thus each of the code vector memories 10, 20, . . . 30 r  provide data in the form of &#34;m&#34; bits which represent the error deviation for each input vector component and the corresponding code vector selected from that memory. The element &#34;a&#34; is chosen such that it provides the most efficient use of the output configuration of the memory. 
     As seen in FIG. 1, there is provided a counter 5 designated as a &#34;n bit counter&#34; where the number n represents the number of search branches that are sequenced in the memory in order to derive the vector code information. Symbol &#34;n&#34; will vary from 0 up to 2 k-1  which would indicate that at its maximum usage the presearch sequence could step through 16 branches in the tree search. In the special case where the codebook is greater than 2 k-1  and less than 2 k , the counter would require reset at the codebook size with additional circuitry. 
     The counter 5 thus provides a count of the code index which is derived from each branch of the tree search code. 
     For each count of the counter 5 there is provided a simultaneous output data from each of the codebook memories which are inserted into the summation circuit means 40. The summation circuit means 40 provides a code vector error function for each count of the counter, that is to say, for each search step through the tree search sequence. 
     Each output step of the search sequence is conveyed to the latch 50 and to the comparison circuit 60 whereby a comparison may be made to select the particular step &#34;n&#34; which provided the minimal error function. After stepping through the 2 k  steps of the tree search sequence, the comparison circuit 60 can select the lowest minimal error function and latch the code index in the latch 70 which represents that particular code vector which provided the minimum error function. 
     Then this code vector from latch 70 can be conveyed as a code index 80 on a data link to a decoding device at a remote location. 
     FIG. 2A is a schematic illustration of how the system may be used for tree search architectures. For example, at the first level, the codebook vector may be a y 0  or y 1 . Then at the next search level the codebook vector may be y 0 ,0 or y 0 ,1. On the same branch of this code vector group, the code vector may be y 1 ,0 or y 1 ,1. Now stepping down further in the branch level, it is seen that at the third branch level, the code vector may be either y 0 ,0,0 or y 0 ,0,1 or y 0 ,1,0 or y 0 ,1,1. Likewise on the other branch at the same level, the codebook vector may be y 1 ,0,0 or y 1 ,0,1 or y 1 ,1,0 or y 1 ,1,1. 
     This tree is referred to as a &#34;binary tree&#34; since each level has two branches. Implementation of this binary tree requires three encoders, with k=1. 
     Using the example shown in FIG. 2B, it can then be seen that the codebook tree structure of multiple levels can be made using larger encoders. For instance, at tree level 1 there might be 16 vector quantities and at tree level 2 there may be as many as 256 vector quantities. This structure could be developed to add further levels with greater refinement. 
     The architectural system using the precalculated memory and the latch compare selection circuitry serves the purpose of finding the best fit vector of dimensions from a predefined codebook of 2 k  vectors of dimensions. These codebook vectors are designed by a vector quantization algorithm for codebook design. There are many different types of algorithms for developing a codebook design, however, the best fit vector is here defined as the minimum error deviation, e n , where: ##EQU2## 
     P i  represents the vector component (or one of the vector components) such as were earlier designated as P 1 , P 2 , etc. 
     The symbol X ni  represents the codebook vector at the nth level of the tree search for that particular input vector component designated as P i . 
     The symbol &#34;r&#34; represents a total number of input vector components such as would be covered from the inputs P 1  through and up to P r . 
     The symbol &#34;a&#34; represents a number between 1 and 2 and is generally equal to the number 2 where it follows the formula of error deviations using the least mean square function. 
     While previously it was necessary to use large amounts of expensive hardware to perform the entire calculations required necessary to calculate all the error measurements for the code vectors stored in memory in addition to requiring all the extra time needed to do these calculations, however with the provision of precalculated component error terms for all of the possible input vector components being stored in memory, it is a quick and simple task to make use of these precalculated component error terms and to proceed through the sequence to select that codebook vector which provides the least distortion or the minimum error function term (index) which can then be transmitted over a data link to a decoder receiver unit for replication. 
     There has been described herein an vector quantizer encoder system which uses a precalculated error codebook system whereby a code vector which presents the minimal distortion or minimal error function can be selected after a codebook tree search to provide an output code index which can be transmitted on a data link for replication by a remote decoder-receiver. The previous need for expensive calculator circuitry and time consuming calculations have now been eliminated, and a rapid inexpensive system has been provided whereby data compression code indices can be sent over a data link to a remote unit for replication in relatively accurate fashion with minimal distortion and with advantageous savings through the use of data compression methods which require simpler and much less expensive bandwidth requirements for line transmission. 
     While the above described system for selecting the best fit vector in a codebook which most closely matches the input vector has been described in one embodiment, there may be provided other functional architectures for the speedy and efficient dispatch of code index vectors to a remote receiver unit. However, it should be understood that other variations of the above described invention may be implemented but which still fall within the framework of the attached claims.