Abstract:
A method for compressing digital sound data in which method a sound signal is divided for encoding into temporal segments and the sound samples of a segment, which are originally presented by N 0  number of bits, are requantized by one or more number of bits which are smaller than N 0,  is characterized in that an upper limit is set for the quantization error, and one of the greatest absolute sound samples of the segment is selected as a fixed point (x p ) on the basis of which said smaller number of bits and the value of the quantization step are defined and such an amount of the sound samples of the segment are quantized by means of them that the upper limit of the quantization error is not exceeded, whereby the samples quantized in this way form a group of values associated to the fixed point (x p ) concerned and quantized by said smaller number of bits and the value of the quantization step.

Description:
FIELD OF THE INVENTION 
       [0001]    The invention deals with a method to process sound information, where the sound signal to be encoded is divided into temporal segments each containing a certain amount of sound samples. 
       BACKGROUND OF THE INVENTION 
       [0002]    Lossy compression techniques are frequently applied to sound and image data. This is due to the fact that human capacity to comprehend information like sound and image is based on over all impression instead of detailed analysis. Examples of sound information compression can be found in the GSM standard, in the MP3 standard as well as in the A- and μ-law algorithms used in leased lines. These methods yield a suitable compression ratio with respect to their applications, which is important because of e.g. limited access and capacity in network connections or because of the requirement for sound quality. 
         [0003]    The GSM method suits best for reproduction of sound by only one speaker, but the sound quality deteriorates substantially in reproducing music. The AMR (Adaptive Multi Rate) method possesses a clearly better sound quality than the GSM method., but the music quality is, however, generally not sufficient and lacks well behind the level achieved by the MP3 method. 
         [0004]    Music can not be reproduced well enough by most of the existing mobile devices due to the insufficient power of the processing components decoding data produced by the more demanding compression algorithms like MP3. In more recent devices support for MP3 decoding is embedded. 
         [0005]    This does not in any way set aside the problem that deals with music reproduction while watching videos in a mobile device. Rather extensive processing power is usually required to decode video data and in addition to this simultaneous good quality music data decoding would be necessary. The 3GPP standard targeted at encoding mobile videos has addressed the sound part by the AMR method, which as mentioned earlier is not sufficient for good quality music reproduction. 
       SUMMARY OF THE INVENTION 
       [0006]    The aim of the invention is to formulate a method to encode and decode sound, which would particularly reduce the number of calculations in decoding sound data and which would therefore be applicable to playing high quality voice and music in mobile devices with low power processors. Another purpose is to come about with a method which can improve the reproduction of music combined with video data in mobile devices. 
         [0007]    To achieve these goals to compress digital sound data, where the sound signal is for decoding divided into temporal segments and the segment sound samples, which have originally been presented by N 0  number of bits will be requantized by one or more number of bits, the number of each is less than N 0 , the present invention provides a method in accordance with the independent claim  1 . The other claims define some embodiments of the method of the present invention. 
         [0008]    In the present invention both encoding and decoding are simple processes calculation wise. 
         [0009]    The method reduces distribution of quantum data at low signal values and on the other hand quantum values less than 8 bits can be utilized. 
         [0010]    One particular advantage of this method is its decompression efficiency of compressed signal values: only one multiplication execution is required after possible lossless decoding of quantum data has been completed. 
         [0011]    In this method the precision of the decoded approximate values tends to maximize in large sound sample values, when e.g. in the A and μ law methods the precision increases as the sound sample values get smaller and furthermore these methods do not exploit variations of contents and lengths in short sound segments. The A and μ law methods typically use tables in the encoding phase because logarithmic calculations would require too much processing power. The method of the present invention does not need tables requiring extra memory. 
     
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         [0012]    The present invention will be addressed in the following pages in more detail with reference to the accompanying drawings, wherein 
           [0013]      FIG. 1  illustrates a schematic example of a sound signal and its division into temporal segments for encoding, 
           [0014]      FIG. 2  illustrates an example of a single segment containing sound samples and 
           [0015]      FIG. 3  illustrates another example of a single segment containing sound samples. 
       
    
    
     DETAILED DESCRIPTION OF THE INVENTION 
       [0016]    A sound signal of  FIG. 1  to be encoded has been divided into temporal segments of variable lengths  1 ,  2 ,  3 , . . . M−1, M. The lengths of these segments may also be the same. 
         [0017]      FIG. 2  shows an example of a segment h 1  consisting of k original sound samples {x 0 , x 1 , x 2 , . . . , x k−1 } h . It is common practice to apply 16 bit precision to digitize a sound signal and also in this example the original sound samples have been digitized by the number of bits N 0 =16. In the method of the present invention the sound samples of the segment originally presented by N 0  bits will be requantized by N number of bits, where N&lt;N 0 . 
         [0018]    In an embodiment a choice is first made which number of bits will be applied to encode the samples of the pertinent segment. N may e.g. be 6, which will result in compression efficiency of 62.5% when N 0 =16 before the final lossless compression. 
         [0019]    Next a fixed point x p  among the segment samples is selected which may be the almost greatest absolute value, which can be chosen so that the greatest absolute value is still expressible by the N number of bits or alternatively it may be the greatest absolute value x max . It is advantageous to perform the following calculations with all the values of x p  satisfying the previous conditions because it is likely that one value of the fixed point x p  will render a signal to noise ratio better that the others. Here we choose x max  as the fixed point and the value of the quantization step q h (N) is calculated by dividing the previous value by the number 2 N −1: 
         [0000]        q   h ( N )= x   max /(2 N −1)   (1) 
         [0020]    Applying this quantization step value the samples can be presented with N bits: 
         [0000]      χ qi   =x   i   /q   h ( N )   (2) 
         [0021]    The decoding process will yield the approximate N-bit sample values accordingly: 
         [0000]        x   i ( q   h )=χ qi   ·q   h    (3) 
         [0022]    Now the original samples will be quantized and decoded deploying all the possible quantization step values resulting from N bits and hence having a certain range of variation [q hMIN , q hMAX ]. The total segment error is calculated for each quantization of the segment samples by every quantization step value, the error being e.g. the sum of the squares of the differences between the original N 0 -bit and the decoded N-bit approximate values based on the respective quantization step values. 
         [0023]    The optimum quantization step value q hOPT  is the value which produces the smallest total error of the segment. This can be expressed e.g. as follows: 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       q 
                       hOPT 
                     
                     = 
                     
                       min 
                        
                       
                         { 
                         
                           
                             ∑ 
                             i 
                           
                            
                           
                             
                               ( 
                               
                                 
                                   x 
                                   i 
                                 
                                 - 
                                 
                                   
                                     x 
                                     i 
                                   
                                    
                                   
                                     ( 
                                     
                                       q 
                                       h 
                                     
                                     ) 
                                   
                                 
                               
                               ) 
                             
                             2 
                           
                         
                         } 
                       
                     
                   
                   , 
                 
               
               
                 
                   ( 
                   4 
                   ) 
                 
               
             
           
         
       
       
         
           
             where 0≦i&lt;k 
           
         
       
     
         [0000]      q hMIN ≦q h &lt;q hMAX    
         [0000]        q   hMIN   =x   max   /q   h ( N ) 
         [0000]        q   hMAX   =x   max   /q   h ( N− 1) 
         [0025]    Besides the sum of the squares of the differences mentioned above the total error can be defined otherwise, e.g. the sum of the absolute differences of the original and the decoded approximate values. 
         [0026]    The maximum value may also be substituted by a value close to the maximum one so that the quantization of the segment values does not exceed the number of bits N chosen. 
         [0027]    Each segment to be encoded will be quantized by the said optimum quantization step of the segment. The encoding of the sound data will produce two series of numbers, the other of which contains the quantized values of the segment samples {{x 0 , x 1 , x 2 , . . . , x k1−1 } 1 , {x 0 , x 1 , x 2 , . . . , x k2−1 } 2 , {x 0 , x 1 , x 2 , . . . , x k2−1 } 3 , . . . , {x 0 , x 1 , x 2 , . . . , x kM−1 } M } and the other consists of the optimal quantization step values of the segments {q 1OPT , q 2OPT , . . . , q MOPT }. 
         [0028]    The latter number series does not necessarily have to use integers. The segments may be of the same or different length. The criterion to choose the number of sound samples and/or the number of bits N for a segment may e.g. be the segment signal to noise ratio after the quantization or the upper limit for the total amount of bits allowed for the quantization as it has been previously described. Other selection criteria may also be deployed. 
         [0029]    In the above example to find the best i.e. the optimal value all the possible values of the quantization step were considered in an orderly fashion. To speed up the search for the quantization step value only a part of the possible quantization step values may be tried out for instance in the following ways: 
         [0030]    a) only every k th  value within certain limits is considered 
         [0031]    b) binary search is applied 
         [0032]    c) a smaller set of values is arbitrarily selected 
         [0033]    It is uncertain whether the best value will be found in any of the speed up cases. This is due to the fact that as the quantization step increases the total segment error may increase or decrease, i.e. the total error may change randomly. It is also possible to try more samples according to some algorithm if the speed up procedure for the segment does not bring about a satisfactory quantization step value. 
         [0034]    Another option is to address all the values within an interval shorter than the interval enclosing all the possible values or to address all the values within several shorter intervals. 
         [0035]    In this method the signal encoding criterion can also be the segment signal to noise ratio to which a certain minimum limit S min  is imposed. Then to achieve this minimum limit it is possible to proceed in many different ways by suitably selecting the segment lengths and the corresponding values of the number of bits N. 
         [0036]    In an embodiment the length of the selected segment is kept constant and the maximum value of the signal to noise ratio S k (N) achievable with N bits is calculated referring to the case described earlier where the total error due to the approximation is the smallest. If S k (N)&lt;S min  the value of N will be increased by one, i.e. N=N+1 and then the corresponding signal to noise ratio S k (N) is calculated as before. This procedure is repeated until the target is reached, in other words until S k (N)≧S min . If the first calculation yielded a signal to noise ratio greater than the minimum limit set, i.e. S k (N)&gt;S min , then the value of N is decreased by one, N=N−1 and then the maximum signal to noise ratio is calculated as before. This procedure is carried on until the goal is attained, S k (N)&lt;S min , in which case the value of N will be set to one greater than the previous value, meaning N=N+1 or the current N value if S k (N)=S min . Here it is obvious that the value of N may be at any time changed by more than the value 1. 
         [0037]    In an embodiment the number of bits N used to quantize the selected segment is chosen to be unchangeable and additionally for the first round of calculations the segment length is set to k=k 0 . Using these as the starting values the greatest signal to noise ratio S N (k) is calculated and if it falls below the set target, that is S N (k)&lt;S min  then the segment length is cut to half, i.e. k=k 0 /2. This procedure is continued until the minimum limit is reached so that S N (k)&gt;S min , in which case the segment value is increased by half of the previously decreased value which leads to a converging series of segment lengths for example as follows: {k 0 , −k 0 /2, −k 0 /4, +k 0 /8, −k 0 /16, +k 0 /32, . . . }, where the negative sign of the value indicates that the segment length has been decreased by that value and the positive sign indicates that the segment length has been increased by that value. The segment length is set to that value of k, which was the most recent to comply with the condition S N (k)&gt;S min  or the value of k giving S N (k)=S min . Other methods can also be applied to alter the segment length. 
         [0038]    The segment division is an essential matter like also the selection of the number of bits and furthermore the fact that the size of the quantization step cannot be fixed beforehand because it depends on the maximum (or near the maximum) signal value of the segment after the number of bits has been first set. The length and the number of bits can be 
         [0039]    a) set in advance or 
         [0040]    b) either one or both can be adaptively determined according to some criterion which may for instance be the minimum limit of the segment signal to noise ratio or some other criterion pertaining to one or several segments. 
         [0041]    In an embodiment both the segment length k and the number of bits N expressing a signal value is changed either simultaneously or alternating in some suitable manner so that any single segment will have its signal to noise ratio at least equal to the set minimum limit. In an embodiment both the segment length k and the number of bits N expressing a signal value is changed either simultaneously or alternating in some suitable manner so that any single segment will have its signal to noise ratio at least equal to the set minimum limit and the total number of bits required to express the signal approximate values by the end of the encoding is the smallest possible. 
         [0042]    In an embodiment the minimum limit of the average signal to noise ratio of two or more segments is used as the encoding criterion. In this case the signal to noise ratio of one or more segments may fall below the minimum limit as other segments exceed the minimum value. 
         [0043]    In an embodiment the upper limit of the total number of bits accumulated as a result of the encoding is used as the criterion of the encoding. Now the embodiments described above may be applied to minimize the total signal error. 
         [0044]    In case the lengths of the segments and/or the number of bits N used for expressing the signal values then the corresponding number series {k 1 , k 2 , k 3 , . . . , k M } and/or {N 1 , N 2 , N 3 , . . . , N M } will be included in the encoding data. 
         [0045]    These number series or the differences between the series members may often be compressed by some lossless compression method to minimize the total number of bits produced. In addition to this it may be possible to still reduce the total number of bits by expressing the signs of the quantum values as a separate series. 
         [0046]    Below several procedures are presented to select the signal samples for the quantization in order to attain more efficient compression ratios compared to the quantization based on the direct selection of all the signal samples. 
         [0047]    In  FIG. 3  in the segment h 2  a fixed point x p  is first selected which can be the absolute maximum or almost the absolute maximum value of the segment samples as described earlier. 
         [0048]    The number of bits N to quantize a sample is set together with either 1) the maximum allowed quantization error of any single sample or 2) the maximum allowed average quantization error of the selected samples or 3) the maximum allowed average quantization error of the selected samples combined with the maximum allowed standard deviation of the quantization error or combined alternatively with some other useful statistical parameters. As described earlier the quantization error may be expressed by means of the signal to noise ratio. 
         [0049]    If the quantization error criterion is applied to a single sample then after each quantization using the symbols defined previously the absolute value of the quantization error is calculated as follows: 
         [0000]        e   i   =|x   i   −x   i ( q   h )|  (5 ) 
         [0050]    The sample is tagged quantized and belonging to the group G p  of the firstly chosen fixed point x p  if the calculated error does not exceed the maximum allowed quantization error e max  that is 
         [0000]        x   i ( q   h )ε G   p , when  e   i   ≦e   max    (6) 
         [0051]    In case some samples were not included in the G p  group the next fixed point x p+1  will be chosen among these samples after which the next fixed point or the sample group G p+1  is made up according to the procedure above. This mode of operation is continued until all the segment samples belong to some sample group. In case there will in the segment be groups with only one member then 1) these groups may be ungrouped i.e. their samples are tagged free belonging to no groups after which the number of bits N will be increased by one and a recalculation is performed addressing these samples or 2) the segment length is altered and a recalculation is executed in part or in all of the groups. 
         [0052]    In  FIG. 3  the two fixed point groups could be formed as follows: G p ={x 1 , x 2 , . . . , x p , x j−1 , . . . x k−3 } h2  and G p+1 ={x 0 , . . . , x j , x p+1 , . . . , x k−2 , x k−1 } h2 . The quantization step values associated with the fixed points could also be encoded based on their differences. 
         [0053]    If the maximum allowed average quantization error serves as the selection criterion then e.g. after having calculated each value of e i  the average error is estimated and compared to the maximum value of the corresponding error and consequently x i  is either tagged to belong to the currently handled group or it still remains a free sample. In the similar fashion in the standard deviation case the corresponding calculation is performed and the comparison is made to the maximum allowed standard deviation. 
         [0054]    In a simple embodiment there are only two fixed points in a segment in which case tagging a sample to a group can be expressed by one bit. In another simple embodiment a group of index series is defined as in the two fixed point case by associating some periodic index series to one fixed point group and hence all the other indices will always belong to the other fixed point group, in which case no additional information is needed for tagging an individual sample to a group. This kind of a periodic index series can be formed to any desired number of fixed points in a segment by calculations by selecting the period length so that the total error of the fixed point group is the smallest e.g. according to the equation (4). 
         [0055]    Suitable index series may also be generated by first encoding the sound signal and at the same time storing all the generated index series and then selecting a suitable smaller number of the most frequently used or almost similar index series and then reencoding the sound signal using and selecting those index series producing the best encoding result, the series of which or their index differences may still be compressed by lossless methods. 
         [0056]    In all cases the final decision to select samples in a segment can be done by comparing the one fixed point case to the several fixed points case, where the criterion might e.g. be an optimal ratio between the compression bit load and the signal to noise ratio of the segment. 
         [0057]    The invention may vary within the scope of the accompanying claims.