Abstract:
The invention proposes an efficient method of determining, in an arbitrary assembly of non-uniformly distributed points, the point which is nearest from a characteristic of a given analog signal. It is particularly applicable to the detection of symbols in a PCM modem. The method comprises the step of considering successive search intervals, each search interval being obtained by splitting up a preceding search interval into two intervals, each interval comprising a number of points, the numbers being equal or different by one, such that one of these two intervals which comprises the received point constitutes the next search interval.

Description:
FIELD OF THE INVENTION 
     The invention relates to a method of searching, in an assembly of non-uniformly distributed points, the point which is the nearest from of a characteristic of a given analog signal. The invention also relates to a receiver comprising means for receiving an analog signal, and decoding means for selecting, in an assembly of non-uniformly distributed points, the point which is the nearest from a characteristic of the received signal. The invention further relates to a transmission system comprising such a receiver. 
     The invention finds important applications, notably in modems of the PCM (Pulse Code Modulation) type, and particularly in modems conforming to the recommendation V.90 of the ITU (International Telecommunication Union). 
     BACKGROUND OF THE INVENTION 
     U.S. Pat. No. 4,143,363 describes a method of determining the quantization level associated with an analog signal by applying a segmented linear logarithmic compression law. This method comprises the step of determining, from an assembly of non-uniformly distributed levels, the level which is the nearest from the amplitude of the received analog signal. The proposed method takes certain properties of the compression law into account: particularly it takes account of the fact that the linear segments each comprise the same number of points. 
     This is a specific method which is connected with the law of distributing points in the assembly considered. Particularly, it is not applicable to the detection of symbols received by a VPCM modem because the constellations used by the PCM modems only comprise certain points of a law for segmented linear logarithmic compression. 
     SUMMARY OF THE INVENTION 
     The invention notably has for its object to provide an efficient method of determining, in an arbitrary assembly of non-uniformly distributed points, the point which is the nearest from a characteristic of a given analog signal. 
     This object is achieved by means of a method as defined in claim  1  of this application. The proposed solution consists of effectuating a dichotomy on the number of points comprised in the search interval. It is independent of the law of distributing points in the considered search assembly. 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS 
     These and other aspects of the invention are apparent from and will be elucidated, by way of non-limitative example, with reference to the embodiment(s) described hereinafter. 
     In the drawings: 
     FIG. 1 shows an embodiment of the transmission system according to the invention, 
     FIG. 2 shows a logarithmic compression law, 
     FIG. 3 shows an embodiment of the constellation used by PCM modems, 
     FIG. 4 shows an organogram of an embodiment of the method according to the invention, 
     FIG. 5 is a block diagram of an embodiment of the receiver according to the invention. 
    
    
     DESCRIPTION OF PREFERRED EMBODIMENTS 
     The PCM modems allow interconnection of a user A connected to a transmission network via an analog connection and a user B connected to the same network via a digital connection. These may be, for example, a user terminal A communicating with a server B of a service provider. 
     FIG. 1 shows an embodiment of such a transmission system. The transmission system of FIG. 1 comprises a digital telecommunication network  1  having two switches  2 A and  2 B. A PCM modem  3 A is connected to the switch  2 A by means of a twisted pair  4 A for transmitting analog signals. A PCM modem  3 B is connected to the switch  2 B by means of a digital connection  4 B, for example, an ISDN connection. This digital connection  4 B may be considered as an extension of the digital transmission network: the switch  2 B thus plays the role of a repeater. 
     In conformity with the recommendation V.90, the PCM modems use constellations constituted by points of a law of segmented linear logarithmic compression, known as the A-law or μ-law. These selected points in the law are referred to as constellation symbols. 
     The segmented linear logarithmic A-laws or μ-laws were originally introduced in A/D and D/A converters of digital switches of telephone networks for speech transmission. They allow a non-uniform quantization of the amplitude of the signal to be transmitted so as to guarantee a constant signal-to-noise ratio independent of the considered amplitude (the quantization levels are closer together as the origin is approached). 
     The positive part of a μ-law has been diagrammatically shown, by way of example, in FIG.  2 . It consists of 8 segments each comprising 16 quantization levels. A point P i  is associated by the μ-law with each quantization level U i . 
     Generally, the symbols of a constellation must be sufficiently spaced so as to allow detection of symbols received with an acceptable error rate. The detection errors are more sensitive to the data than to speech (a detection error means the restitution of an erroneous data, while a speech detection error means an error in the restituted sound level). In particular it is not possible to use all the points of the A-law or μ-law (adapted to speech transmission) for forming a constellation used by modems for transmitting data. It is for this reason that only certain points of the A-law or μ-law are selected for forming the constellations used by the VPCM modems. 
     FIG. 3 shows an embodiment of the constellation that can be used for PCM modems. For the sake of simplicity, the constellation is limited to 12 amplitude symbols C(i) with i=0, . . . , 11. The constellation is organized in a descending order, i.e. the smallest index i=0 refers to the point in the constellation having the largest amplitude C(0). 
     In a descending transmission from B to A, the modem B emits binary words. Each emitted binary word U i  is associated with a symbol of the constellation used. These binary words are received by the converter  2 A and converted into analog signals by applying an inverse expansion law for said compression law. The analog signals thus formed are transmitted through the connection  4 A. For each received signal, the modem A must retrieve, in the constellation used, the symbol which is the nearest from the amplitude of the received signal, i.e. the index p which verifies: 
     
       
         | C ( p )−| S ∥=Min i∈{0, . . . ,k−1}   |C ( i )−| S∥   
       
     
     where k is the number of symbols of the constellation and | S | is the amplitude of the received signal. 
     In accordance with the invention, successive search intervals I j  centered at |S| are considered. The search interval I j+1  is obtained by dividing the search interval I j  into two intervals each comprising a number of symbols said numbers of points being equal or different by one. The interval I j+1  is that one of the two obtained intervals which comprises the amplitude point |S|. 
     An embodiment of the search method according to the invention will now be described with reference to FIG.  4 . To this end: a search interval I j  is defined by the index jm of the symbol having the lowest amplitude C(jm) comprised in I j , and by the index jM of the symbol having the largest amplitude C(jM) comprised in I j:   
     
       
         I j =[C(jm),C(jM)] with jm&gt;jM 
       
     
     N j  is the number of constellation symbols comprised in the search interval I j , Ω j  is the index of the symbol considered as the central symbol for dividing the search interval I j  into two. Ω j  is chosen to be E(N j /2) so as to have the same number of symbols in the two intervals when this is possible, i.e. when N j  is even. When N j  is odd, one of the two intervals will comprise one symbol more than the other. 
     The search method is initialized with the following values (case  10 ): 
     
       
           I   1m   =k− 1 ,I   1M =0 ,N   1   =k,Ω   1   =E ( N   1 /2). 
       
     
     The successive search intervals are then obtained in the following manner for j≧1 (case  20 ):               S        ≥     C                   (     Ω   j     )         ⇒     {                   I     j   +   1       =       [       C                   (     I       (     j   +   1     )                   m       )       ,     C                   (     I       (     j   +   1     )                   M       )         ]     =     [       C                   (     Ω   j     )       ,     C                   (     I   jM     )         ]                   Nj   =         I       (     j   +   1     )                   m       -     I       (     j   +   1     )                   M       +   1     =       Ω   j     -     I   jM     +   1                     Ω     j   +   1       =         I       (     j   +   1     )                   M       +     E        [       N     j   +   1       2     ]         =       I   jM     +     E        [       N     j   +   1       2     ]                        
             S          &lt;     C                   (     Ω   j     )         ⇒     {             I     j   +   1       =       [       C                   (     I       (     j   +   1     )                   m       )       ,     C                   (     I       (     j   +   1     )                   M       )         ]     =     [       C                   (     I   jm     )       ,     C                   (     Ω   j     )         ]                   Nj   =         I       (     j   +   1     )                   m       -     I       (     j   +   1     )                   M       +   1     =       I   jm     -     Ω   j     +   1                     Ω     j   +   1       =         I       (     j   +   1     )                   M       +     E        [       N     j   +   1       2     ]         =       Ω   j     +     E        [       N     j   +   1       2     ]                                                
     When the search interval obtained comprises not more than two symbols (N j =2; case  30 ), the search index p is the index of the symbol whose amplitude is most proximate to |S|: 
      if | C ( I   jm )−| S∥&gt;|C ( I   jM )−| S|   
     then p=I jM  (case  40 ) 
     if not, p=I jm  (case  50 ). 
     FIG. 3 shows the successive search intervals I 1  to I 5  which are necessary for determining the index p=3 of the symbol whose amplitude C(3) is the nearest from the amplitude |S| of the received signal. 
     FIG. 5 shows, by way of example, a block diagram of an embodiment of the receiver  50  according to the invention. It comprises conventional means  100  for receiving analog signals and decoding means  200  for selecting, in the constellation, the symbol C(p) which is the nearest in amplitude from the received signal, and for determining the binary sequence U p  transmitted by the transmitter  3 B, which corresponds to this symbol in conformity with the logarithmic law used. Advantageously, these decoding means  200  are constituted by conventional storage and computing means. 
     Although the invention has been described within the scope of the V.90 standard, it is not limited to this standard. Generally, it is applicable to the search of the point which is the nearest from of a characteristic of a received signal in an assembly of non-uniformly distributed points. The law for distributing the points may be arbitrary.