Depth-first algebraic-codebook search for fast coding of speech

A method of encoding a sound signal, comprising the steps of:

• providing a codebook circuit for forming a codebook including a set of codevectors A.sub.k each defining a plurality of different positions p and comprising N non-zero-amplitude pulses each assignable to predetermined valid positions p of the codevector;
• providing a device for conducting in said codebook a depth-first search involving (a) a partition of the N non-zero-amplitude pulses into a number M of subsets each comprising at least one non-zero-amplitude pulse, and (b) a tree structure including nodes representative of the valid positions p of the N non-zero-amplitude pulses and defining a plurality of search levels each associated to one of the M subsets, each search level being further associated to a given pulse-ordering rule and to a given selection criterion;
• said depth-first search conducting step itself comprising the steps of:
• in a first search level of the tree structure,
• choosing at least one of said N non-zero-amplitude pulses in relation to ,the associated pulse-ordering rule to form the associated subset;
• selecting at least one of the valid positions p of said at least one non-zero-amplitude pulse in relation to the associated selection criterion to define at least one path through the nodes of the tree structure;
• in each subsequent search level of the tree structure,
• choosing at least one of said non-zero-amplitude pulses not previously chosen in relation to the associated pulse-ordering rule to form the associated subset;
• and
• selecting at least one of the valid positions p of said at least one non-zero-amplitude pulse of the associated subset in relation to the associated selection criterion to extend said at least one path through the nodes of the tree structure;
• wherein each path defined at the first search level and extended during the subsequent search levels determines the respective positions p of the N non-zero-amplitude pulses of a codevector A.sub.k constituting a candidate codevector in view of encoding the sound signal.

A system for encoding a sound signal, comprising:

• a codebook including a set of codevectors A.sub.k each defining a plurality of different positions p and comprising N non-zero-amplitude pulses each assignable to predetermined valid positions p of the codevector;
• a device for conducting in said codebook a depth-first search involving (a) a partition of the N non-zero-amplitude pulses into a number M of subsets each comprising at least one non-zero-amplitude pulse, and (b) a tree structure including nodes representative of the valid positions p of the N non-zero-amplitude pulses and defining a plurality of search levels each associated to one of the M subsets, each search level being further associated to a given pulse-ordering rule and to a given selection criterion;
• said depth-first codebook search conducting device comprising:
• for a first search level of the tree structure,
• first means for choosing at least one of said N non-zero-amplitude pulses in relation to the associated pulse-ordering rule to form the associated subset;
• first means for selecting at least one of the valid positions p of said at least one non-zero-amplitude pulse in relation to the associated selection criterion to define at least one path through the nodes of the tree structure;
• for each subsequent search level of the tree structure,
• second means for choosing at least one of said non-zero-amplitude pulses not previously chosen in relation to the associated pulse-ordering function to form the associated subset;
• and
• second means for selecting, in said subsequent search level, at least one of the valid positions p of said at least one non-zero-amplitude pulse of the associated subset in relation to the associated selection criterion to extend said at least one path through the nodes of the tree structure;
• wherein each path defined at the first search level and extended during the subsequent search levels determines the respective positions p of the N non-zero-amplitude pulses of a codevector A.sub.k constituting a candidate codevector in view of encoding the sound signal.

A cellular communication system for servicing a large geographical area divided into a plurality of cells, comprising:

• mobile transmitter/receiver units;
• cellular base stations respectively situated in said cells;
• means for controlling communication between the cellular base stations;
• a bidirectional wireless communication sub-system between each mobile unit situated in one cell and the cellular base station of said one cell, said bidirectional wireless communication sub-system comprising in both the mobile unit and the cellular base station (a) a transmitter including means for encoding a speech signal and means for transmitting the encoded speech signal, and (b) a receiver including means for receiving a transmitted encoded speech signal and means for decoding the received encoded speech signal;
• wherein said speech signal encoding means comprises a device for conducting a depth-first search in a codebook in view of encoding a sound signal, wherein:
• said codebook comprises a set of codevectors A.sub.k each defining a plurality of different positions p and comprising N non-zero-amplitude pulses each assignable to predetermined valid positions p of the codevector;
• said depth-first search involves (a) a partition of the N non-zero-amplitude pulses into a number M of subsets each comprising at least one non-zero-amplitude pulse, and (b) a tree structure including nodes representative of the valid positions p of the N non-zero-amplitude pulses and defining a plurality of search levels each associated to one of the M subsets, each search level being further associated to a given pulse-ordering rule and to a given selection criterion;
• said depth-first codebook search conducting device comprising:
• for a first search level of the tree structure,
• first means for choosing at least one of said N non-zero-amplitude pulses in relation to the associated pulse-ordering rule to form the associated subset;
• first means for selecting at least one of the valid positions p of said at least one non-zero-amplitude pulse in relation to the associated selection criterion to define at least one path through the nodes of the tree structure;
• for each subsequent search level of the tree structure,
• second means for choosing at least one of said non-zero-amplitude pulses not previously chosen in relation to the associated pulse-ordering function to form the associated subset;
• and
• second means for selecting, in said subsequent search level, at least one of the valid positions p of said at least one non-zero-amplitude pulse of the associated subset in relation to the associated selection criterion to extend said at least one path through the nodes of the tree structure;
• wherein each path defined at the first search level and extended during the subsequent search levels determines the respective positions p of the N non-zero-amplitude pulses of a codevector A.sub.k constituting a candidate codevector in view of encoding the sound signal.