DE19609170A1

DE19609170A1 - Verfahren zur Durchführung einer "Tiefe-Zuerst"-Suche in einem Codebuch zur Codierung eines Geräusch- bzw. Klangsignals, Vorrichtung zur Durchführung dieses Verfahrens sowie zellulares Kommunikationssystem mit einer derartigen Vorrichtung

Info

Publication number: DE19609170A1
Application number: DE19609170A
Authority: DE
Inventors: Jean-Pierre Adoul; Claude Laflamme
Original assignee: Universite de Sherbrooke
Current assignee: Universite de Sherbrooke
Priority date: 1995-03-10
Filing date: 1996-03-09
Publication date: 1996-09-19
Anticipated expiration: 2016-03-10
Also published as: EP0813736A1; JP3160852B2; GB2299001A; CN1181151A; ES2112808A1; KR19980702890A; CA2213740A1; PT813736E; KR100299408B1; SE9600918L; ES2112808B1; AU707307B2; DE19609170B4; SE520554C2; IT1285305B1; IN187842B; RU2175454C2; GB9605123D0; AU4781196A; ATE193392T1

Description

Die Erfindung betrifft ein Verfahren zur Durchführung einer "Tiefe-Zuerst" ("Depth-First") -Suche in einem Codebuch zur Codierung eines Geräusch- bzw. Klangsignales, eine Vorrichtung zur Durchführung dieses Verfahrens sowie ein zellulares Kommunikationssystem mit einer derartigen Vorrichtung.

Allgemein befaßt sich die vorliegende Erfindung mit einem verbesserten Verfahren zur digitalen Codierung eines Geräusch- bzw. Klangsignales, insbesondere, aber nicht ausschließlich, eines Sprachsignales, welches übertragen und synthetisiert werden soll.

Für zahlreiche Anwendungsfälle, beispielsweise für die Übertragung von Stimmen über Satelliten, beweglichen Landfunk, digitales Radio oder gepackt arbeitende Netze ("packed networks"), für die Sprachspeicherung, Spracher kennung und -steuerung sowie drahtloses Telefonieren, besteht ein zunehmender Bedarf an effizienten digitalen Sprachcodierverfahren mit gutem Kompromiß zwischen subjek tiver Qualität und Bitrate.

Eines der besten bekannten Verfahren, mit welchem sich ein guter Kompromiß zwischen Qualität und Bitrate erzielen läßt, ist das sogenannte "Code-Excited-Linear-Prediction (CELP)"-Verfahren. Bei diesem Verfahren wird das Sprach signal abgetastet und in aufeinanderfolgenden Blocks von L Proben (genannt: Vektoren) verarbeitet. L ist dabei eine vorherbestimmte Zahl. Das CELP-Verfahren verwendet ein Codebuch.

Ein Codebuch ist im CELP-Kontext ein mit Indices versehener Satz von L Proben langen Folgen, die als L-dimensionale Codevektoren bezeichnet werden. Das Codebuch umfaßt einen Index k, der von 1 bis M läuft. Dabei stellt M die Größe des Codebuchs dar, die manchmal als Bitzahl b ausgedrückt wird:

M = 2^b.

Ein Codebuch kann in einem physischen Speicher (beispiels weise einer Nachschlagtabelle) gespeichert werden oder einem Mechanismus Gebrauch machen, welcher den Index mit einem entsprechenden Codevektor verknüpft (beispielsweise von einer Formel).

Zur Synthetisierung von Sprache nach dem CELP-Verfahren wird jeder Block von Sprachproben dadurch synthetisiert, daß der entsprechende Codevektor aus dem Codebuch durch zeitvariierende Filter, welche die spektralen Charakte istika des Sprachsignals modellieren, gefiltert wird. Am Codierende wird das synthetische Ausgangssignal für alle Codevektoren oder einen Untersatz der Codevektoren aus dem Codebuch errechnet (Codebuch-Suche). Der erhaltene Codevektor ist derjenige, der dasjenige synthetische Aus gangssignal erzeugt, welches nach einem durch Wahrnehmung gewichteten Verzerrungsmaßstab dem ursprünglichen Sprach signal am nächsten kommt.

Eine erste Art Codebuch sind die sogenannten "stochasti schen" Codebücher. Ein Nachteil derartiger Codebücher besteht darin, daß sie häufig einen erheblichen physischen Speicherbedarf haben. Sie sind stochastisch, das heißt in dem Sinne zufällig, daß der Weg von dem Index zu dem zugeordneten Codevektor über Nachschlagtabellen läuft, die das Ergebnis zufällig erzeugter Zahlen oder statisti scher Verfahren sind, die auf große Sprach-Trainingssätze angewandt werden. Die Größe von stochastischen Codebüchern wird im wesentlichen durch die Komplexität der Speicherung und/oder Suche beschränkt.

Eine zweite Art Codebuch sind die algebraischen Codebücher. Im Gegensatz zu stochastischen Codebüchern sind algebra ische Codebücher nicht zufällig und erfordern keinen wesentlichen Speicherplatz. Ein algebraisches Codebuch ist ein Satz von mit Indices versehenen Codevektoren, wobei die Amplituden und Positionen der Impulse des k-ten Codevektors durch eine Regel aus einem entsprechenden Index k abgeleitet werden kann, die keine oder nur minimale physische Speicherung erfordert. Demzufolge ist die Größe von algebraischen Codebüchern nicht durch die Anforderungen an den Speicherplatz beschränkt. Algebraische Codebücher können also für eine effiziente Suche ausgelegt werden.

Aufgabe der vorliegenden Erfindung ist es daher, ein Ver fahren, eine Vorrichtung und ein zellulares Kommunikations system der eingangs genannten Art zu schaffen, mit welchen die Komplexität der Codebuch-Suche beim Codieren eines Geräusch- bzw. Klangsignales reduziert ist, wobei dieses Verfahren, diese Vorrichtung und dieses zellulare Kommuni kationssystem bei einer großen Klasse von Codebüchern anwendbar sein sollen.

Diese Aufgabe wird erfindungsgemäß gelöst durch ein Verfahren zur Durchführung einer "Tiefe-Zuerst"-Suche in einem Codebuch zur Codierung eines Geräusch- bzw. Klangsignales, bei welchem:
das Codebuch einen Satz von Codevektoren A_k umfaßt, die jeweils eine Vielzahl unterschiedlicher Positionen p de finieren und N Nicht-Null-Amplituden-Impulse umfassen, von denen jeder einer vorherbestimmten gültigen Position p des Codevektors zuordenbar ist;
wobei die "Tiefe-Zuerst"-Suche eine Baumstruktur benutzt, die eine Anzahl M geordneter Niveaus definiert, von denen jedes Niveau m einer vorherbestimmten Anzahl N_m von Nicht-Null-Amplituden-Impulsen, N_m<1, zugeordnet ist, wobei die Summe der vorherbestimmten Zahlen, die allen M Niveaus zugeordnet sind, gleich der Zahl N der Nicht-Null- Amplituden-Impulse ist, die sich in den Codevektoren befinden, und wobei ferner jedes Niveau m der Baumstruktur außerdem einem Weg-Aufbau-Vorgang zugeordnet ist mit einer vorgegebenen Impulsordnungsregel und mit einem vorgegebenen Auswahlkriterium;
wobei das "Tiefe-Zuerst"-Codebuch-Suchverfahren die folgenden Schritte umfaßt:

- in einem Niveau 1 der Baustruktur besteht der zugeordnete Weg-Aufbau-Vorgang in folgendem:
eine Zahl N₁ der N Nicht-Null-Amplituden-Impulse wird entsprechend der zugeordneten Impulsordnungsregel gewählt;
mindestens eine der gültigen Positionen p der N₁ Nicht- Null-Amplituden-Impulse wird entsprechend dem zugeordne ten Auswahlkriterium so gewählt, daß mindestens ein Kandidatenweg auf dem Niveau -1 definiert wird;
- in einem Niveau m der Baumstruktur definiert der zuge ordnete Weg-Aufbau-Vorgang rekursiv einen Kandidatenweg auf dem Niveau -m, indem ein Kandidatenweg auf dem Niveau -(m-1) durch die folgenden Unterschritte verlängert wird:
N_m der Nicht-Null-Amplituden-Impulse, die nicht schon zuvor im Verlaufe des Aufbaues des Weges auf dem Niveau -(m-1) ausgewählt wurden, werden entsprechend der zuge ordneten Impulsordnungsregel gewählt;
mindestens eine der gültigen Positionen p der N_m Nicht- Null-Amplituden-Impulse wird entsprechend dem zugeord neten Auswahlkriterium so ausgewählt, daß mindestens ein Kandidatenweg auf dem Niveau -m gebildet wird;
wobei ein Kandidatenweg auf dem Niveau -M, der auf dem Niveau -1 entstanden ist und bei den Weg-Aufbau-Vor gängen, welche darauffolgenden Niveaus der Baumstruk tur zugeordnet sind, verlängert wurde, die entsprechen den Positionen p der N Nicht-Null-Amplituden-Impulse eines Codevektors bestimmt und auf diese Weise einen Kandidaten-Codevektor A_k definiert.

Diese Aufgabe wird außerdem gelöst durch ein Verfahren zur Durchführung einer "Tiefe-Zuerst"-Suche in einem Codebuch zur Codierung eines Geräusch- bzw. Klangsig nals, bei dem:
das Codebuch einen Satz von Codevektoren A_k umfaßt, die jeweils eine Mehrzahl unterschiedlicher Positionen p de finieren und N Nicht-Null-Amplituden-Impulse umfassen, von denen jeder vorherbestimmten gültigen Positionen p des Codevektors zuordenbar ist;
wobei die "Tiefe-Zuerst"-Suche Gebrauch macht von (a) einer Unterteilung der N Nicht-Null-Amplituden-Impulse in eine Anzahl M von Untersätzen, von denen jeder mindestens einen Nicht-Null-Amplituden-Impuls umfaßt, und (b) einer Baumstruktur, welche Knotenpunkte enthält, welche für die gültigen Positionen p der N Nicht-Null-Amplituden-Impulse repräsentativ sind und eine Mehrzahl von Suchniveaus definieren, von denen jedes einem der M Untersätze zugeord net ist, und wobei jedes Suchniveau außerdem einer vorge gebenen Impulsordnungsregel und einem vorgegebenen Selek tionskriterium zugeordnet ist;
wobei das "Tiefe-Zuerst"-Codebuch-Suchverfahren folgende Schritte umfaßt:

- in einem ersten Suchniveau der Baumstruktur:
Wählen von mindestens einem der N Nicht-Null-Amplitu den-Impulse entsprechend der zugeordneten Impulsordnungs regel zur Bildung des zugeordneten Untersatzes;
Auswählen von mindestens einer der gültigen Positionen p des mindestens einen Nicht-Null-Amplituden-Impulses entsprechend dem zugeordneten Auswahlkriterium, wodurch mindestens ein Weg durch die Knotenpunkte der Baumstruk tur definiert wird;
- in jedem darauffolgenden Suchniveau der Baumstruktur:
Wählen von mindestens einem der Nicht-Null-Amplituden- Impulse, die nicht zuvor schon ausgewählt wurden, ent sprechend der zugeordneten Impulsordnungsregel zur Bildung des zugeordneten Untersatzes; und
Auswählen von mindestens einer der gültigen Positionen p des mindestens einem Nicht-Null-Amplituden-Impulses des zugeordneten Untersatzes entsprechend dem zugeordneten Auswahlkriterium, wodurch der mindestens eine Weg durch die Knotenpunkte der Baumstruktur verlängert wird;

wobei jeder Weg, der an dem ersten Suchniveau definiert und bei den darauffolgenden Suchniveaus verlängert wurde, die entsprechenden Positionen p der N Nicht-Null-Amplituden- Impulse eines Codevektors A_k bestimmt, der einen Kan ditaten-Codevektor für die Codierung des Geräusch- bzw. Klangsignales bildet.

Die oben geschilderte Aufgabe wird ferner gelöst durch eine Vorrichtung zur Durchführung einer "Tiefe-Zuerst"-Suche in einem Codebuch zur Codierung eines Geräusch- oder Klang signals, bei der:
das Codebuch einen Satz von Codevektoren A_k umfaßt, die jeweils eine Mehrzahl unterschiedlicher Positionen p de finieren und N Nicht-Null-Amplituden-Impulse umfassen, von denen jeder vorherbestimmten gültigen Positionen p des Codevektors zuordenbar ist;
die "Tiefe-Zuerst"-Suche Gebrauch macht von (a) der Unterteilung der N Nicht-Null-Amplituden-Impulse in eine Anzahl M von Untersätzen, von denen jeder mindestens einen Nicht-Null-Amplituden-Impuls umfaßt, und (b) einer Baum struktur, welche Knotenpunkte enthält, welche für die gültigen Positionen p der N Nicht-Null-Amplituden-Impulse repräsentativ sind und eine Mehrzahl von Suchniveaus definieren, von denen jedes einem der M Untersätze zugeord net ist und außerdem einer vorgegebenen Pulsordnungsregel und einem vorgegebenen Auswahlkriterium zugeordnet ist;
wobei die "Tiefe-Zuerst"-Codebuch-Suchvorrichtung umfaßt:

- für ein erstes Suchniveau der Baumstruktur:
eine erste Einrichtung zum Wählen von mindestens einem der N Nicht-Null-Amplituden-Impulse entsprechend der zugeordneten Impulsordnungsregel zur Bildung des zugeord neten Untersatzes;
eine erste Einrichtung zur Auswahl von mindestens einer der gültigen Positionen p des mindestens einen Nicht- Null-Amplituden-Impulses entsprechend dem zugeordneten Auswahlkriterium zum Definieren von mindestens einem Weg durch die Knotenpunkte der Baumstruktur;
- für jedes darauffolgende Suchniveau der Baumstruktur:
eine zweite Einrichtung zum Wählen von mindesten einem der Nicht-Null-Amplituden-Impulse, die nicht zuvor schon gewählt wurde, entsprechend der zugeordneten Impuls ordnungsfunktion zur Bildung des zugeordneten Untersatzes;
eine zweite Einrichtung zur Auswahl in dem darauf folgen den Suchniveau von mindestens einer der gültigen Positio nen p des mindestens einen Nicht-Null-Amplituden-Impulses des zugeordneten Untersatzes entsprechend dem zugeord neten Auswahlkriterium, wodurch der mindestens eine Weg durch die Knotenpunkte der Baumstruktur verlängert wird,

wobei jeder Weg, der in dem ersten Suchniveau definiert und bei den darauffolgenden Suchniveaus verlängert wurde, die entsprechenden Positionen p der N Nicht-Null-Amplituden- Impulse eines Codevektors A_k bestimmt, der einen Kandida ten-Codevektor zur Codierung des Geräusch- bzw. Klangsig nales bildet.

Schließlich wird die oben geschilderte Aufgabe gelöst durch ein zellulares Kommunikationssystem zur Bedienung eines großen geografischen Gebietes, welches in eine Mehrzahl von Zellen unterteilt ist, mit:
mobilen Transmitter/Empfänger-Einheiten;
zellularen Basisstationen, die jeweils in den Zellen an geordnet sind;
Einrichtungen zur Steuerung der Kommunikation zwischen den zellularen Basisstationen;
einem bidirektionen Funk-Kommunikations-Untersystem zwischen jeder mobilen Einheit, die in einer Zelle angeord net ist, und der zellularen Basisstation dieser einen Zelle, welches sowohl in der mobilen Einheit als auch in der zellularen Basisstation umfaßt: (a) einen Sender, der eine Einrichtung zur Codierung eines Sprachsignales und eine Einrichtung zum Senden des codierten Sprachsignales enthält; und (b) einen Empfänger, der eine Einrichtung zum Empfang eines gesendeten codierten Sprachsignales und eine Einrichtung zur Decodierung des empfangenen codierten Sprachsignales enthält;
wobei die Codiereinrichtung für das Sprachsignal eine Vorrichtung umfaßt, welche eine "Tiefe-Zuerst"-Suche in einem Codebuch für die Codierung des Sprachsignales durchführt, bei welcher
das Codebuch einen Satz von Codevektoren A_k umfaßt, die jeweils eine Mehrzahl von unterschiedlichen Positionen p definieren und N Nicht-Null-Amplituden-Impulse umfassen, die jeweils bestimmten gültigen Positionen p des Codevek tors zuordenbar sind;
die "Tiefe-Zuerst"-Codebuch-Suche Gebbrauch macht von: (a) einer Unterteilung der N Nicht-Null-Amplituden-Impulse in eine Anzahl M von Untersätzen, die jeweils mindestens einen Nicht-Null-Amplituden-Impuls umfassen; und (b) einer Baum struktur, welche Knotenpunkte enthält, die für die gültigen Positionen p der N Nicht-Null-Amplituden-Impulse repräsen tativ sind und eine Mehrzahl von Suchniveaus definieren, die jeweils einem der M Untersätze und außerdem einer vorgegebenen Impuls-Ordnungsregel und einem vorgegebenen Auswahlkriterium zugeordnet sind;
wobei die "Tiefe-Zuerst"-Codebuch-Suchvorrichtung umfaßt:

- für ein erstes Suchniveau der Baumstruktur:
eine erste Einrichtung zum Wählen von mindestens einem der N Nicht-Null-Amplituden-Impulse entsprechend der zugeordneten Impulsordnungsregel zur Bildung des zugeord neten Untersatzes;
eine erste Einrichtung zur Auswahl von mindestens einer der gültigen Positionen p des mindestens einen Nicht- Null-Amplituden- Impulses entsprechend dem zugeordneten Auswahlkriterium zum Definieren von mindestens einem Weg durch die Knotenpunkte der Baumstruktur;
- für jedes darauffolgende Suchniveau der Baumstruktur:
eine zweite Einrichtung zum Wählen von mindestens einem der Nicht-Null-Amplituden-Impulse, die nicht schon zuvor gewählt wurden, entsprechend der zugeordneten Impuls- Ordnungsregel zur Bildung des zugeordneten Untersatzes; und
eine zweite Einrichtung zur Auswahl von mindestens einer der gültige Positionen p des mindestens einen Nicht-Null- Amplituden-Impulses des zugeordneten Untersatzes in dem darauffolgenden Suchniveau entsprechend dem zuge ordneten Auswahlkriterium, wodurch der mindestens eine Weg durch die Knotenpunkte der Baumstruktur verlängert wird;

wobei jeder Weg, der an dem ersten Suchniveau definiert und bei den darauffolgenden Suchniveaus verlängert wurde, die entsprechenden Positionen p der N Nicht-Null-Amplituden- Impulse eines Codevektors A_k bestimmt, welcher zur Codierung des Geräusch- bzw. Klangsignales einen Kandidaten- Codevektor bildet.

Die Erfindung wird nachfolgend anhand von Ausführungsbei spielen unter Bezug auf die Zeichnung näher erläutert; es zeigen

Fig. 1 ein schematisches Blockdiagramm eines bevorzug ten Ausführungsbeispieles eines erfindungsge mäßen Codiersystemes, welches eine Impulsposi tions-Wahrscheinlichkeitsschätzeinrichtung und eine optimierende Steuereinrichtung umfaßt;

Fig. 2 ein schematisches Blockdiagramm eines Decodier systemes, welches dem Codiersystem von Fig. 1 zugeordnet ist;

Fig. 3 eine schematische Darstellung einer Mehrzahl von verschachtelten Schleifen, die bei der op timierenden Kontrolleinrichtung des Codiersys temes von Fig. 1 zur Errechnung optimaler Codevektoren verwendet wird;

Fig. 4a eine Baumstruktur, an der beispielhaft einige Merkmale des "verschachtelten Schleifen"-Such verfahrens von Fig. 3 erläutert werden;

Fig. 4b die Baumstruktur von Fig. 4a, wenn die Verar beitung auf tieferen Niveaus davon abhängig gemacht wird, daß bestimmte Schwellwerte über schritten werden; dies ist ein schnelleres Ver fahren zur Erforschung des Baumes, indem man sich nur auf die vielversprechendsten Gebiete dieses Baumes konzentriert;

Fig. 5 die Art, wie das "Tiefe-Zuerst"-Suchverfahren durch eine Baumstruktur zu bestimmten Kombinatio nen von Impulspositionen fortschreitet; das Beispiel betrifft ein 10-Impuls-Codebuch mit 40-Positions-Codevektoren, entworfen nach verschachtelten Einfach-Impuls-Permutationen;

Fig. 6 ein schematisches Flußdiagramm, welches die Funktionsweise der Impulspositions-Wahrschein lichkeitsschätzeinrichtung und der optimierenden Steuereinrichtung von Fig. 1 zeigt;

Fig. 7 ein schematisches Blockdiagramm, welches die Infrastruktur eines typischen zellularen Kommu nikationssystemes darstellt.

Nachfolgend wird die Anwendung des erfindungsgemäßen "Tiefe-Zuerst"-Codebuch-Suchverfahrens und der erfindungs gemäßen Vorrichtung bei einem zellularen Kommunikations system als nicht beschränkendes Beispiel erläutert. Es sei jedoch darauf hingewiesen, daß dieses Verfahren und diese Vorrichtung mit denselben Vorteilen bei vielen anderen Arten von Kommunikationssystemen eingesetzt werden können, wo eine Codierung von Geräusch- bzw. Klangsignalen erforderlich ist.

Bei einem zellularen Kommunikationssystem, wie es mit dem Bezugszeichen 1 (Fig. 7) bezeichnet ist, wird die Telekommunikation über große geographische Gebiet hinweg dadurch gewährleistet, daß ein großes Gebiet in eine Anzahl kleinerer Zellen unterteilt wird. Jede Zelle hat eine zellulare Basisstation 2, welche Radio-Signalkanäle sowie Audio- und Datenkanäle bereitstellt.

Die Radio-Signalkanäle werden dazu verwendet, mobile Radio telefone (mobile Transmitter/Empfängereinheiten), wie mit 3 bezeichnet, innerhalb der Grenzen der Erfassungs zone (Zelle) der zellularen Basisstation zu "pagen" und Rufe zu anderen Radiotelefonen 3 entweder innerhalb oder außerhalb der Zelle der Basisstation oder auf ein anderes Netzwerk, wie beispielsweise das öffentliche Telefonnetz (PSTN) 4 zu plazieren.

Sobald ein Radiotelefon 3 einen Ruf erfolgreich plaziert oder empfangen hat, wird mit der zellularen Basisstation 2, welche der Zelle entspricht, in der das Radiotelefon 3 sich befindet, ein Audio- oder Datenkanal eingerichtet. Über diesen Audio- oder Datenkanal findet die Kommunikation zwischen der Basisstation 2 und dem Radiotelefon 3 statt. Das Radiotelefon 3 kann außerdem Steuer- oder Zeitinfor mationen über den Signalkanal erhalten, während ein Ruf abgewickelt wird.

Wenn ein Radiotelefon 3 während eines Anrufes eine Zelle verläßt und in eine andere Zelle eintritt, übergibt das Radiotelefon den Ruf an einen verfügbaren Audio- oder Datenkanal in der neuen Zelle. Wenn kein Anruf abgewickelt wird, wird in ähnlicher Weise eine Kontrollbotschaft über den Signalkanal gesandt, so daß das Radiotelefon 3 sich bei der Basisstation 2, die der neuen Zelle zugeordnet ist, anmeldet. Auf diese Weise ist eine mobile Kommunika tion über große geografische Gebiete hinweg möglich.

Das zellulare Kommunikationssystem 1 umfaßt außerdem ein Terminal 5, welches die Kommunikation zwischen den zellu laren Basisstationen 2 und dem PSTN 4, beispielsweise wäh rend einer Kommunikation zwischen einem Radiotelefon 3 und dem PSTN 4, oder zwischen einem Radiotelefon 3 in einer ersten Zelle und einem Radiotelefon 3 in einer zweiten Zelle steuert.

Natürlich ist ein bidirektionales Funkradio-Subkommunika tionssystem erforderlich, welches eine Kommunikation zwi schen jedem Radiotelefon 3, das sich in einer Zelle be findet, und der zellularen Basisstation 2 dieser Zelle ermöglicht. Ein derartiges bidirektionales Funkradio- Kommunikationssystem umfaßt typischerweise sowohl im Radio telefon 3 als auch in der zellularen Basisstation 2 (a) einen Sender, welcher das Sprachsignal codiert und das codierte Sprachsignal über Antennen, wie sie beispiels weise mit den Bezugszeichen 6 oder 7 gekennzeichnet sind, überträgt, und (b) einen Empfänger, welcher gesendete, codierte Sprachsignale über dieselben Antennen 6 bzw. 7 empfängt und die empfangenen codierten Sprachsignale decodiert. Die Stimmcodierung ist, wie dem Fachmann bekannt, notwendig, um die Bandbreite zu reduzieren, die zur Übertragung von Sprache über das bidirektionale Funkradio-Kommunikationssystem, das heißt, zwischen einem Radiotelefon 3 und einer Basisstation 2, erforderlich ist.

Das Ziel der vorliegenden Erfindung besteht darin, ein effizientes digitales Sprachcodierverfahren zu schaffen, welches einen guten Kompromiß zwischen subjektiver Quali tät und Bitrate erzielt, beispielsweise für die bidirek tionale Übertragung von Sprachsignalen zwischen einer zellularen Basisstation 2 und einem Radiotelefon 3 über einen Audio- oder Datenkanal. Fig. 1 ist ein schemati sches Blockdiagramm einer digitalen Sprachcodiervorrich tung, die zur Ausführung dieses effizienten Verfahrens geeignet ist.

Das Sprachcodiersystem von Fig. 1 ist dieselbe Codier vorrichtung, wie sie in Fig. 1 der US-Patentanmeldung 07/927 528 dargestellt ist, welcher jedoch gemäß der vor liegenden Erfindung eine Impulspositions-Schätzeinrich tung 112 hinzugefügt ist. Die US-Patentanmeldung 07/927 528 wurde am 10. September 1992 für eine Erfindung eingereicht, welche den Titel trägt "Dynamic Code Book for Efficient Speech Coding Based on Algebraic Codes".

Das analoge Eingangs-Sprachsignal wird abgetastet und blockweise verarbeitet. Allerdings sei angemerkt, daß die vorliegende Erfindung nicht auf die Anwendung bei Sprachsignalen beschränkt ist. Es kommt auch die Codie rung anderer Arten von Geräusch- bzw. Klangsignalen in Frage.

Bei dem dargestellten Ausführungsbeispiel umfaßt der Block der eingegebenen Sprachprobe S (Fig. 1) L aufeinander folgende Proben. In der CELP-Literatur wird L als die "Unterrahmen" (subframe)-Länge bezeichnet; sie liegt typi scherweise zwischen 20 und 80. Die Blocks aus L Proben werden als L-dimensionale Vektoren bezeichnet. Verschiedene L-dimensionale Vektoren werden im Verlauf des Codiervor ganges erzeugt. Eine Liste dieser Vektoren, die in den Fig. 1 und 2 erscheinen, sowie eine Liste gesendeter Parameter, folgen unten:

Liste der wichtigsten L-dimensionalen Vektoren

S Eingangs-Sprachvektor
R′ Höhen-entfernter Restvektor
X Zielvektor
D rückwärts gefilterter Zielvektor
A_k Codevektor des Index k aus dem algebraischen Codebuch; und
C_k Innovationsvektor (gefilterter Codevektor).

Liste der gesendeten Parameter

k Codevektor-Index (Eingangssignal des algebrai schen Codebuchs);
g Verstärkung;
STP Kurzzeit-Vorhersageparameter (welche A(z) defi nieren) und
LTP Langzeit-Vorhersageparameter (welche eine Höhen verstärkung b und eine Höhenverzögerung T de finieren).

Es erscheint zweckmäßig, zunächst die Sprachcodiereinrich tung von Fig. 2 zu beschreiben, in welcher die verschie denen Schritte dargestellt sind, die zwischen dem digitalen Eingangssignal (Eingangssignal des Demultiplexors 205) und der ausgegebenen Sprachprobe (Ausgang des Synthese filters 204) ausgeführt werden.

Der Demultiplexor 205 extrahiert vier unterschiedliche Parameter aus der binären Information, die über einen digitalen Eingangskanal empfangen werden, nämlich den Index k, die Verstärkung g, die Kurzzeit-Vorhersagepara meter STP und die Langzeit-Vorhersageparameter LTP. Der laufende L-dimensionale Vektor S des Sprachsignales wird auf der Basis dieser vier Parameter synthetisiert, wie nachfolgend erläutert wird.

Die Sprachcodiervorrichtung von Fig. 2 umfaßt ein dyna misches Codebuch 208, welches sich aus einem algebraischen Codegenerator 201 und einem adaptiven Vorfilter 202 zu sammensetzt, einen Verstärker 206, einen Addierer 207, eine Langzeit-Vorhersageeinrichtung 203 und ein Synthese filter 204.

Im ersten Schritt erzeugt der algebraische Codegenerator 201 einen Codevektor A_k entsprechend dem empfangenen Index k.

Im zweiten Schritt wird der Codevektor A_k durch das adap tive Vorfilter 202 verarbeitet, welches mit den Kurzzeit- Vorhersageparametern STP versorgt ist. Dabei wird ein Ausgangs-Innovationsvektor C_k erzeugt. Der Zweck des adaptiven Vorfilters 202 besteht darin, den Frequenzge halt des Ausgangs-Innovationsvektors C_k dynamisch zu kontrollieren, um die Sprachqualität zu verbessern, das heißt, um die hörbare Verzerrung zu reduzieren, die durch Frequenzen verursacht werden, welche dem menschlichen Ohr unangenehm sind. Typische Übertragungsfunktionen F(z) für das adaptive Vorfilter 202 sind unten angegeben:

F_a(z) ist ein Formanten-Vorfilter, bei welchem 0<τ₁<τ₂<1 Konstanten sind. Dieses Vorfilter verstärkt die Formantenbe reiche und arbeitet insbesondere bei Coderaten unterhalb von 5 kbit/s sehr effektiv.

F_b(z) ist ein Höhen-Vorfilter, wobei T die zeitvariieren de Höhen-Verzögerung und b₀ entweder eine Konstante oder gleich dem quantisierten Langzeit-Höhen-Vorhersage parameter aus dem laufenden oder vorhergehenden Unterrahmen ist. F_b(z) verstärkt harmonische Höhenfrequenzen bei allen Übertragungsraten effektiv. Daher enthält F(z) typi scherweise ein Höhen-Vorfilter, welches manchmal mit einem Formanten-Vorfilter, nämlich F(z) = F_a(z)F_b(z) kombiniert ist. Andere Formen von Vorfiltern können jedoch ebenfalls mit Nutzen eingesetzt werden.

Gemäß der CELP-Technik wird die Ausgangs-Sprachsignalprobe S dadurch erhalten, daß zuerst der Innovationsvektor C_k aus dem Codebuch 208 mit der Verstärkung g durch den Ver stärker 206 skaliert wird. Der Addierer 207 addiert dann die skalierte Wellenform gC_k zu dem Ausgangssignal E (der Langzeit-Vorhersagekomponente der Signalerregung des Syn thesefilters 204) einer Langzeit-Vorhersageeinrichtung 203, welcher die LTP-Parameter zugeführt werden und die in einer Rückkopplungsschleife liegt und eine Transfer funktion B(z) aufweist, die folgendermaßen definiert ist:

B(z) = bz^-T.

Hierbei sind b und T die oben definierte Höhenverstärkung bzw. -verzögerung.

Die Vorhersageeinrichtung 203 ist ein Filter mit einer Transferfunktion, welche in Übereinstimmung mit den zuletzt empfangenen LTP-Parametern b und T ist. Sie modelliert die Höhen-Periodizität der Sprache. Sie führt die geeig nete Höhenverstärkung b und -verzögerung T der Proben ein. Das zusammengesetzte Signal E + gC_k bildet die Signalerregung des Synthesefilters 204, welches eine Trans ferfunktion 1/A(z) aufweist. Das Filter 204 sorgt für die korrekte Spektrum-Formung entsprechend den zuletzte empfangenen STP-Parametern. Genauer modelliert das Filter 204 die resonanten Frequenzen (Formanten) der Sprache. Der Ausgangsblock ist das synthetisierte abgetastete Sprachsignal, welches mit einer geeigneten anti-pseudony misierenden Filterung nach bekannten Verfahren in ein analoges Signal umgewandelt werden kann.

Es gibt viele Arten, ein algebraisches Codebuch 208 zu entwerfen. Bei der vorliegenden Erfindung setzt sich das algebraische Codebuch 208 aus Codevektoren zusammen, welche N Impulse mit einer von 0 abweichenden Amplitude (kurz Nicht-Null-Impulse) aufweisen.

P_i und S_pi seien die Position bzw. die Amplitude des i-ten Nicht-Null-Impulses. Es sei weiter angenommen, daß die Amplitude S_pi bekannt ist, entweder weil die i-te Amplitude fest ist oder weil es eine Methode gibt, vor der Codevektor-Suche S_pi zu wählen.

Mit "Track i", kurz als T_i bezeichnet, sei der Satz von Positionen gemeint, den pi zwischen 1 und L einnehmen kann. Typische Sätze von "Tracks" sind unten angegeben, wobei L mit 40 angenommen ist.

Das erste Beispiel ist eine Konstruktionsweise, die in der oben erwähnten US-Patentanmeldung 07/927 528 erstmals eingeführt wurde und als "Interleaved Single Pulse Permu tations" (ISPP) bezeichnet wird. Bei dem ersten Ausfüh rungsbeispiel dieser Konstruktionsweise, die mit ISPP (40, 5) bezeichnet ist, wird ein Satz von 40 Positionen in 5 wechselseitig verzahnte "Tracks" von jeweils 40/5 = 8 gültigen Positionen unterteilt. Um die 8 = 2³ gültigen Positionen eines gegebenen Impulses zu spezifizieren, werden 3 Bits benötigt. Demzufolge werden insgesamt 5 × 3 = 15 Codierbits benötigt, um für diese spezielle alge braische Codebuch-Struktur Impulspositionen zu spezifizie ren.

Bauweise 1: ISPP (40, 5)

Dieses ISPP ist in dem Sinne vollständig, als jede der 40 Positionen mit einem und nur einem "Track" verknüpft ist. Es gibt viele Arten, eine Codebuch-Struktur aus einem oder mehreren ISPP so abzuleiten, daß bestimmten Anforde rungen hinsichtlich der Anzahl von Impulsen oder Codier bits entsprochen werden kann. Beispielsweise läßt sich ein 4-Impuls-Codebuch aus dem ISPP (40, 5) dadurch ab leiten, daß einfach der "Track" 5 ignoriert wird oder daß die Vereinigung der "Tracks" 4 und 5 als einziger "Track" betrachtet wird. Die Konstruktionsbeispiele 2 und 3 zeigen weitere Möglichkeiten vollständiger ISPP- Bauweisen.

Bauweise 2: ISPP (40, 10)

Bauweise 3: ISPP (48, 12)

Dabei ist zu beachten, daß bei der Konstruktionsweise 3 die letzte Impulsposition der "Tracks" T5 bis T12 außerhalb der Unterrahmen-Länge L = 40 fällt. In einem derartigen Falle wird der letzte Impuls einfach ignoriert.

Bauweise 4: Summe von zwei ISPP (40, 1)

Bei dem Konstruktionsbeispiel 4 lassen die "Tracks" T1 und T2 jede beliebige der 40 Positionen zu. Zu beachten ist, daß die Positionen der "Tracks" T1 und T2 überlappen. Wenn mehrere Impulse denselben Platz einnehmen, werden ihre Amplituden einfach addiert.

Eine große Vielzahl von Codebüchern kann um das allgemeine Thema der ISPP-Bauweise herum gebaut werden.

Es folgt eine Erläuterung des Kodierprinzips.

Das abgetastete Sprachsignal S wird auf einer Block-für- Block-Basis durch das Codiersystem von Fig. 1 codiert, welches in 11 mit dem Bezugszeichen 102 bis 112 versehene Moduln unterteilt ist. Die Funktion und Wirkungsweise der meisten dieser Moduln sind gegenüber dem, was in der US- Patentanmeldung 07/927 528 beschrieben ist, unverändert. Demzufolge konzentriert sich die nachfolgende Beschreibung auf das, was gegenüber der Offenbarung der US-Patentanmel dung 07/927 528 neu ist, wenn auch zumindest kurz Funktion und Wirkungsweise von jedem Modul erläutert werden.

Für jeden Block von L Proben des Sprachsignales wird ein Satz linearer Vorhersage-Codeparameter (LPC), genannt Kurzzeit-Vorhersageparameter (STP), nach einem bekannten Verfahren durch eine LPC-Spektrum-Analysiereinrichtung 102 erzeugt. Genauer modelliert die Analysiereinrichtung 102 die spektralen Charakteristiken von jedem Block S von L-Proben.

Der eingegebene Block S von L Proben wird durch ein Auf hellungsfilter 103 aufgehellt, welches die folgende Trans ferfunktion, basierend auf den laufenden Werten der STP- Parameter, aufweist:

Hierin ist a₀ = 1 und Z die übliche Variable der sogenann ten z-Transform. Wie in Fig. 1 dargestellt, erzeugt das Aufhellfilter 103 einen Restvektor R.

Eine Höhen-Extraktionseinrichtung 104 wird dazu verwendet, die LTP-Parameter, nämlich die Höhen-Verzögerung T und die Höhen-Verstärkung g, zu errechnen und zu quantisieren. Der Anfangszustand der Extraktionseinrichtung 104 wird ebenfalls auf einen Wert FS aus einer Anfangszustands-Ex traktionseinrichtung 110 eingestellt. Eine detaillierte Prozedur zur Errechnung und Quantisierung der LTP-Para meter ist in der US-Patentanmeldung 07/927 528 beschrieben; es wird unterstellt, daß diese dem Fachmann bekannt ist. Demzufolge wird sie vorliegend nicht näher erklärt.

Eine Filterantwort-Charakterisiereinrichtung 105 (Fig. 1) wird mit den STP- und LTP-Parametern versorgt und er rechnet eine Filterantwort-Charakterisierung FRC zur Verwendung in den nachfolgenden Schritten. Die FRC-Infor mation besteht aus den nachfolgenden drei Komponenten, wobei n = 1, 2, . . . L.

*f(n): Antwort von F(z).
Beachte, daß F(z) allgemein das Höhen-Vorfilter enthält.
*h(n) : Antwort von

auf f(n), wobei τ
ein Wahrnehmungsfaktor ist.
Allgemeiner ist h(n) die Impulsantwort von F(z) W(z)/A(z), wobei es sich um die Kaskade des Vorfilters F(z), des Wahrnehmungs-Gewichtungs filters W(z) und des Synthesefilters 1/A(z) handelt. Beachte, daß F(z) und 1/A(z) dieselben Filter sind, wie sie im Decoder eingesetzt werden.
*U(ÿ): Autokorrelation von h(n) entsprechend dem nachfol genden Ausdruck:

für 1 i L und i j L; h(n)= 0 für n 1.

Die Langzeit-Vorhersageeinrichtung 106 wird mit dem ver gangenen Erregungssignal (das heißt, E + gCk des vorherge henden Unterrahmens) versorgt und bildet die neue E-Kompo nente unter Verwendung der richtigen Höhenverzögerung T und -verstärkung b.

Der Anfangszustand des Wahrnehmungsfilters 107 wird auf den Wert FS eingestellt, der von der Anfangszustand-Extrak tionseinrichtung 110 zur Verfügung gestellt wird. Der Höhen-entfernte Restvektor R′ = R - E, der von einer Sub traktionseinrichtung 121 (Fig. 1) errechnet wird, wird dann dem Wahrnehmungsfilter 107 zugeführt, an dessen Aus gang ein Zielvektor X erhalten wird. Wie in Fig. 1 dar gestellt, werden die STP-Parameter dem Filter 107 zuge führt, wodurch dessen Transferfunktion entsprechend diesen Parametern variiert wird. Grundsätzlich gilt X = R′ - P, wobei P den Anteil der Langzeitvorhersage (LTP) einschließlich des "Klingelns" ("Ringing") aus vergangenen Erregungen darstellt. Das MSE-Kriterium, welches auf den Fehler Δ anzuwenden ist, kann nunmehr in der folgenden Matrix-Darstellung festgehalten werden:

Hierin sind Δ = ′-S′ und ′ bzw. S′ sind bzw. S nach der Verarbeitung durch ein Wahrnehmungs-Gewichtungsfilter, welches die folgende Übertragungsfunktion aufweist:

Hier ist τ = 0,8 eine Wahrnehmungskonstante; H ist eine niedrigere dreieckige L × L-Töplitz-Matrix, die aus der h(n)-Antwort folgendermaßen gebildet wird: Der Ausdruck h(0) nimmt die Matrix-Diagonale ein und die Ausdrücke h(1), h(2), . . . und h(L -1) nehmen die entsprechenden tieferen Diagonalen ein.

Durch das Filter 108 von Fig. 1 wird ein Rückwärts-Filter schritt ausgeführt. Setzt man die Ableitung der obigen Gleichung nach der Verstärkung g gleich 0, ergibt sich die optimale Verstärkung wie folgt:

Für diesen Wert von g wird die Minimalisierung:

Ziel ist es, den speziellen Index k zu finden, für welchen die Minimalisierung erreicht wird. Dabei ist zu beachten, daß derselbe Index auch durch Maximierung der folgenden Größe erreicht werden kann, da ||X||² eine feste Größe ist:

Dabei ist D = (XH) und α_k² = ||A_kH^T||².

In dem Rückwärtsfilter 108 wird ein rückwärts gefilterter Zielvektor D = (XH) errechnet. Der Ausdruck "Rückwärts filterung" für diesen Vorgang rührt aus der Interpretation von (XH) als Filterung des zeitumgekehrten X.

Der Zweck der optimierenden Steuereinrichtung 109 besteht darin, die in dem algebraischen Codebuch verfügbaren Code vektoren zu suchen und den besten Codevektor zur Codie rung des laufenden L-Proben-Blockes auszuwählen. Das Haupt kriterium zum Auswählen der besten Codevektoren aus einem Satz von Codevektoren, die jeweils N Nicht-Null-Impulse aufweisen, läßt sich in Form eines zu maximierenden Ver hältnisses angeben:

Haupt-Auswahlkriterium:

Dabei ist

Hierin hat A_k N Nicht-Null-Amplituden-Impulse. Der Zähler in der obigen Gleichung ist das Quadrat von

Hier ist D der rückwärts gefilterte Zielvektor und A_k ist der algebraische Codevektor mit N Nicht-Null-Impulsen der Amplituden S_pi.

Der Nenner ist ein Energieterm, der folgendermaßen ausge drückt werden kann:

Hier ist U(p_i, p_j) die Korrelation, die zwei Einheits- Amplituden-Impulsen, einer am Ort p_i und der andere am Ort p_j, zugeordnet ist. Diese Matrix wird entsprechend der obigen Gleichung in dem Filterantwort-Charakterisier modul 105 errechnet und ist in dem Satz von Parametern enthalten, die in dem Blockdiagramm von Fig. 1 als FRC bezeichnet sind.

Eine schnelle Methode zur Errechnung dieses Nenners macht von den N-fach verschachtelten Schleifen Gebrauch, die in Fig. 4 dargestellt sind. In dieser wird die verein fachte Notation S(i) und SS(i,j) anstelle der entspre chenden Größen "S_pi" und "S_piS_pj" verwendet. Die Errechnung des Nenners α_k² ist der am meisten Zeit ver brauchende Vorgang. Die Rechenvorgänge, die zu α_k² bei tragen und in jeder Schleife der Fig. 4 ausgeführt werden, können auf getrennten Zeilen von der äußersten Schleife zur innersten Schleife folgendermaßen niedergeschrieben werden:

Dabei ist pi die Position des i-ten Nicht-Null-Impulses.

Die obige Gleichung kann vereinfacht werden, wenn durch die optimierende Steuereinrichtung 109 eine gewisse Vorberechnung durchgeführt wird, bei welcher die Matrix U(i,j), welche von der Filterantwort-Charakterisierein richtung 105 bereitgestellt wird, in eine Matrix U′(i,j) entsprechend der folgenden Beziehung umgewandelt wird:

U′(j, k) = S_j S_k U(j,k).

Hier ist S_k die Amplitude, die für einen individuellen Impuls an der Position k nach der Quantisierung der ent sprechenden Amplitudenschätzung (wie weiter unten beschrie ben) gewählt wird. Der Faktor 2 wird in dem Rest der Dis kussion ignoriert, um die Gleichungen zu vereinfachen.

Mit der neuen Matrix U′(j,k) läßt sich der Rechenvorgang (vergl. Fig. 3) für jede Schleife des schnellen Algorithmus auf einer getrennten Zeile, von der äußeren zur innersten Schleife, wie folgt niederschreiben:

Fig. 4a und 4b zeigen zwei Beispiele einer Baumstruktur, anhand derer einige Merkmale der "verschachtelte-Schleifen- Suche"-Technik illustriert werden, die soeben beschrieben und in Fig. 3 dargestellt wurde, um sie in Gegensatz zur vorliegenden Erfindung zu stellen. Die Endknotenpunkte an der Unterseite des Baumes von Fig. 4a zeigen alle mög lichen Kombinationen von Impulspositionen für ein Beispiel mit 5 Impulsen (N = 5), wobei jeder Impuls eine von vier möglichen Positionen einnehmen kann. Die erschöpfende "verschachtelte-Schleifen-Suche"-Technik verläuft durch die Baumknotenpunkte im wesentlichen von links nach rechts, wie angedeutet. Ein Nachteil des "verschachtelte-Schleifen- Suche"-Lösungsweges besteht darin, daß die Komplexität der Suche als Funktion der Anzahl von Impulsen N anwächst. Um Codebücher mit einer größeren Anzahl N von Impulsen verarbeiten zu können, muß man sich mit einer Partial durchsuchung des Codebuches begnügen. Fig. 4b zeigt den selben Baum, wobei eine schnellere Suche dadurch erzielt wird, daß man sich nur auf das vielversprechendste Ge biet des Baumes konzentriert. Genauer ist das Fortschrei ten zu den tieferen Niveaus nicht systematisch sondern davon abhängig, ob bestimmte vorgegebene Schwellwerte überschritten werden.

Nunmehr sei die Aufmerksamkeit dem alternativen schnelleren Verfahren zugewandt, welches Gegenstand der vorliegenden Erfindung ist und durch die Impulspositions-Wahrschein lichkeitsschätzeinrichtung 112 und die optimierende Steu ereinrichtung 109 von Fig. 1 durchgeführt wird. Zunächst werden die allgemeinen Merkmale dieses Verfahrens beschrie ben. Danach wird eine Anzahl typischer Illustrationsbei spiele für das schnellere Verfahren erläutert.

Ziel der Suche ist es, den Codevektor mit dem besten Satz von N Impulspositionen zu bestimmen, wobei angenommen wird, daß die Amplituden der Impulse entweder fest sind oder aufgrund eines signalbasierenden Mechanismus vor der Suche ausgewählt wurden, wie dies in der US-Patentan meldung 08/383 968, eingereicht am 6. Februar 1995, be schrieben ist. Das Haupt-Auswahlkriterium ist die Maximie rung des oben erwähnten Verhältnisses Q_k.

Um die Komplexität der Suche zu reduzieren, werden die Impulspositionen jeweils als N_k Impulse zu einer bestimm ten Zeit bestimmt. Genauer werden die N verfügbaren Impulse in M nicht-leere Untersätze von N_m Impulse aufgeteilt (Schritt 601 von Fig. 1), derart, daß N₁ + N₂ . . . + N_m . . . + N_M = N. Eine bestimmte Wahl von Positionen für die ersten J = N₁ + N₂ . . . + N_m-1 betrachteten Impulse wird als "Niveau-m"-Weg bzw. Weg der Länge J bezeichnet. Das Hauptkriterium für einen Weg von J Impuls-Positionen ist das Verhältnis Q_k(J), wenn nur die J relevanten Impulse betrachtet werden.

Die Suche beginnt mit dem Untersatz Nr. 1 und schreitet mit darauffolgenden Untersätzen entsprechend einer Baum struktur fort, wobei der Untersatz m an dem m-ten Niveau des Baumes durchsucht wird.

Der Zweck der Suche am Niveau 1 besteht darin, die N₁ Impulse des Untersatzes Nr. 1 zu betrachten sowie deren gültige Positionen, um einen oder eine Anzahl von Kan didatenwegen der Länge N₁ zu bestimmen, bei welchen es sich um die Baum-Knotenpunkte im Niveau 1 handelt.

Der Weg an jedem Endknotenpunkt des Niveaus m-1 wird auf die Länge N₁ + N₂ . . . + N_m am Niveau m verlängert, indem N_m neue Impulse und deren gültige Positionen be trachtet werden. Ein oder eine ganze Anzahl von verlänger ten Kandidatenwegen werden betrachtet und bilden so die Niveau-m-Knotenpunkte.

Der beste Codevektor entspricht demjenigen Weg der Länge N, welcher das Kriterium Q_k(N) hinsichtlich aller Niveau- M-Knotenpunkte maximiert.

Während in der oben erwähnten US-Patentanmeldung 08/927 528 die Impulse (oder "Tracks") in einer vorherbestimmten Reihenfolge (i = 1, 2, . . . N) erforscht werden, werden sie in der vorliegenden Erfindung in unterschiedlicher Reihenfolge betrachtet. Tatsächlich können sie entspre chend derjenigen Reihenfolge betrachtet werden, welche unter den besonderen Umständen zu einer beliebigen Zeit während der Suche für die erfolgversprechendste gehalten wird. Hierzu wird ein neuer chronologischer Index n (n = 1, 2, . . . N) verwendet, und die ID(Identifikations)-Zahl des n-ten betrachteten Impulses in der Suche wird durch die "Impulsordnungsfunktion": i = i(n) angegeben. Beispiels weise könnte der Suchweg bei einem 5-Impuls-Codebuch zu einer bestimmten Zeit entsprechend der nachfolgenden Impulsordnungsfunktion verlaufen:

n = 1 2 3 4 5 chronologischer Index
i = 4 3 1 5 2 Impuls-(oder "Track"-) ID.

Um in intelligenter Weise zu raten, welche Impulsordnung zu einer beliebigen Zeit vielversprechender ist, führt die vorliegende Erfindung einen "Impulspositions-Wahrschein lichkeitsschätzvektor" B ein. Dieser basiert auf sprachbe zogenen Signalen. Die p-te Komponente B_p dieses Schätz vektors B charakterisiert die Wahrscheinlichkeit, daß ein Impuls die Position p (p = 1, 2, . . . L) in dem besten Codevektor, nach dem gesucht wird, einnimmt. Dieser beste Codevektor ist noch immer unbekannt, und es ist der Zweck der vorliegenden Erfindung zu offenbaren, wie auf einige Eigenschaften dieses besten Codevektors von den sprachbe zogenen Signalen geschlossen werden kann.

Der Schätzvektor B kann folgendermaßen verwendet werden:
Zunächst dient der Schätzvektor B als Basis, um zu bestim men, für welche "Tracks" i oder j die Impulsposition leich ter zu erraten ist. Der "Track", für welchen die Impulspo sition leichter zu erraten ist, sollte als erster verar beitet werden. Diese Eigenschaft wird in der Impulsordnungs regel beim Auswählen der N_m Impulse in den ersten Niveaus der Baumstruktur häufig verwendet.

Der Schätzvektor B gibt zweitens für einen bestimmten "Track" die relative Wahrscheinlichkeit jeder gültigen Position an. Diese Eigenschaft wird vorteilhafterweise als Auswahlkriterium in den paar ersten Niveaus der Baum struktur anstelle des Haupt-Auswahlkriteriums Q_k(j) verwendet, welches in den ersten paar Niveaus ohne hin auf zu wenige Impulse einwirkt, um bei der Auswahl gültiger Positionen verläßlich zu arbeiten.

Die bevorzugte Methode, den Impulspositions-Wahrscheinlich keits-Schätzvektor B aus sprachbezogenen Signalen zu er mitteln, besteht darin, die Summe des normalisierten rück wärts-gefilterten Zielvektors D;

sowie des normalisierten Höhen-entfernten Restsignals R′:

zu errechnen, wodurch der Impulspositions-Wahrscheinlich keitsschätzvektor B erhalten wird:

Hier ist β eine feste Konstante mit einem typischen Wert von 1/2 (ß wird zwischen 0 und 1 gewählt, je nach dem Prozentsatz von Nicht-Null-Impulsen, die in dem algebra ischen Code verwendet werden).

An dieser Stelle sei darauf hingewiesen, daß derselbe Schätzvektor in einem unterschiedlichen Kontext und zu einem anderen Zweck in der anhängigen US-Patentanmeldung 08/383 968 verwendet wird, die am 6. Februar 1995 für eine Erfindung mit dem Titel "Algebraic Codebook with Signal- Selected Pulse Amplitudes for Fast Coding of Speech" hinterlegt wurde. Diese beschreibt ein Verfahren, a priori eine nahezu optimale Kombination von Impulsamplituden auszuwählen. Dies kann im Kontext einer algebraischen Codebuch-Konstruktion verwendet werden, wo Nicht-Null- Impulsamplituden einen von q Werten annehmen können, wobei q<1 ist. Diese Beobachtung bestätigt, daß die Entdeckung von guten Schätzern, wie dies B ist und die von dem Signal selbst abgeleitet werden können, für eine effiziente Sprachcodierung von tiefer Bedeutung ist. Tatsächlich gibt es über die Schätzer für entweder die Positionen oder die Amplituden hinaus Schätzer für den Codevektor A_k selbst. Daher liegt jedes Suchverfahren, welches sowohl die Prinzipien der anhängigen US-Patentan meldung 08/383 968 als auch diejenigen der vorliegenden Anmeldung anwendet, eindeutig innerhalb des Grundgedankens der vorliegenden Erfindung. Nachfolgend wird ein Beispiel für ein typisches kombiniertes Verfahren innerhalb des Grundgedankens der vorliegenden Erfindung gegeben. Weiter oben wurde bereits darauf hingewiesen, daß dann, wenn zwei oder mehr Impulse aus einander überlappenden "Tracks" dieselbe Position im Rahmen teilen, diese addiert werden sollten. Dieser Kompromiß zwischen Position und Amplitude kann durch eine gitterartige Suche gemeinsam optimiert werden.

Aus Zweckmäßigkeitsgründen werden sowohl die Konstanten als auch die Variablen, die bereits definiert wurden, unten aufgelistet.

Liste der Konstanten

Liste der Variablen

Nunmehr sei eine Anzahl typischer Beispiele für "Tiefe- Zuerst"-Suchen betrachtet:

Suchverfahren Nr. 1 Algebraisches Codebuch

L = 40; N = 5
ISPP (40, 5); (i.e.: L₁ = L₂ = . . . L₅ = 8)

Suchvorgang

Regel R1

Die zehn Wege, eine erste Impulsposition p_i(1) für den Weg-Aufbauvorgang im Niveau -1 zu wählen, besteht darin, jeden der 5 "Tracks" der Reihe nach zu betrachten und für jeden "Track" der Reihe nach eine der beiden Positio nen zu wählen, welche B_p für den jeweils betrachteten "Track" maximieren.

Regel R2

Regel 2 definiert die Impulsordnungsfunktion, die für vier an den Niveaus 2 und 3 betrachtete Impulse zu benutzen ist, wie folgt: Lege die vier verbleibenden Indices auf einem Kreis aus und numeriere diese im Uhrzeigersinn um, wobei rechts von dem i(1)-Impuls (das heißt, der Impulszahl des speziellen betrachteten Knotenpunktes auf dem Niveau -1) begonnen wird.

Nunmehr wenden wir uns einem zweiten Beispiel der "Tiefe- Zuerst"-Codebuchsuche zu, die Suchverfahren Nr. 2 genannt wird und die deutlich die "Tiefe-Zuerst"-Grundsätze ver anschaulicht.

Suchverfahren Nr. 2 Algebraisches Codebuch

L = 40; N = 10
ISPP (40, 10); (i.e.: L₁ = L₂ = . . . L₁0 = 4)

Suchvorgang

Regel R3

Wähle den Impuls i(1) und wähle dessen Position entspre chend dem Maximum von B_p über alle p. Wähle für i(2) der Reihe nach jeden der verbleibenden 9 Impulse. Das Auswahl kriterium für ein vorgegebenen i(2) besteht darin, die Position zu wählen, welche B_p innerhalb seines "Tracks" maximiert.

Regel R4

Am Ende des Niveaus 1. Die gesamte Impulsordnungsfunktion wird dadurch bestimmt, daß die 8 verbleibenden Indices n auf einem Kreis ausgelegt und im Uhrzeigersinn umnumeriert werden, wobei rechts von i(2) begonnen wird.

Das Suchverfahren Nr. 2 ist in den Fig. 5 und 6 veran schaulicht. Fig. 5 zeigt die Baumstruktur des "Tiefe- Zuerst"-Suchverfahrens Nr. 2, welches auf ein 10-Impuls- Codebuch von 40 Positions-Codevektoren angewandt wird, konstruiert nach wechselseitig verzahnten Einzel-Impuls- Permutationen. Das entsprechende Flußdiagramm ist in Fig. 6 dargestellt.

Die L=40 Positionen werden in 10 "Tracks" unterteilt, die jeweils einem der N=10 Nicht-Null-Amplituden-Impulse der Codevektoren zugeordnet sind. Die 10 "Tracks" sind entsprechend den N wechselseitig verzahnten Einzel-Impuls- Permutationen verzahnt.

Schritt 601

Der oben beschriebene Impulspositons-Wahrscheinlichkeits schätzvektor B wird errechnet.

Schritt 602

Die Position p des maximalen Absolutwertes des geschätzten B_p wird errechnet.

Schritt 603 (Beginn der Wegaufbau-Vorgänge auf dem Niveau -1)

Wähle den Impuls (i.e. "Track") i(1) und wähle dessen gültige Position so aus, daß diese der im Schritt 602 (vergl. 501 in Fig. 5) gefundenen Position entspricht.

Schritt 604 (Ende der Wegaufbau-Vorgänge auf dem Niveau -1)

Wähle für i(2) der Reihe nach jeden der verbleibenden 9 Impulse. Das Auswahlkriterium für ein gegebenes i(2) besteht darin, die Position auszuwählen, welche B_p inner halb des "Tracks" des genannten vorgegebenen i(2) maximiert. Auf diese Weise werden 9 unterschiedliche Kandidatenwege auf dem Niveau -1 erzeugt (vergl. 502 in Fig. 5). Jeder der Kandidatenwege auf dem Niveau -1 wird danach durch da rauffolgende Niveaus der Baumstruktur so verlängert, daß 9 unterschiedliche Kandidaten-Codevektoren gebildet werden. Der Zweck des Niveaus -1 besteht offensichtlich darin, 9 gute Startpaare von Impulsen herauszugreifen, die auf der B-Schätzung basieren. Aus diesem Grunde werden die Wegaufbau-Vorgänge auf dem Niveau -a "signalbasierendes Impulssieben" in Fig. 5 genannt.

Schritt 605 (Regel R4)

Um Rechenzeit zu sparen, wird die in den darauffolgenden 4 Niveaus zu verwendende Impulsordnung voreingestellt. Die Impulsordnungsfunktion i(n) für n = 3, 4, . . .10 wird dadurch bestimmt, daß die 8 verbleibenden Indices n auf einem Kreis ausgelegt und im Uhrzeigersinn umnumeriert werden, wobei rechts von i(2) begonnen wird. Entsprechend dieser Ordnung werden die Impulse i(3) und i(4) für das Niveau -2 gewählt, wobei die Impulse i(5) und i(6) bereits für das Niveau -3 gewählt sind, usw.

Schritte 606, 607, 608, 609 (Niveaus 2 bis 5)

Die Niveaus 2 bis 5 sind auf Effizienz ausgelegt und folgen identischen Prozeduren. Eine erschöpfende Suche wird auf alle 16 Kombinationen der 4 Positionen der beiden betrach teten Impulse (vergl. 503 in Fig. 5) entsprechend dem zugeordneten Auswahlkriterium Q_k(2m) angewandt, wobei m = 2, 3, 4, 5 die Niveaunummer ist.

Da aus jedem Wegaufbau-Vorgang (vergl. 504 in Fig. 5), der mit den Niveaus 2 bis 5 (i.e. Verzweigungsfaktor 1) verknüpft ist, nur ein einziger Kandidatenweg resultiert, wächst die Komplexität der Suche im wesentlichen nur linear mit der Gesamtzahl von Impulsen. Aus diesem Grunde läßt sich die in den Niveaus 2 bis 5 durchgeführte Suche genau als "Tiefe-Zuerst"-Suche charakterisieren. Baumsuch techniken variieren stark in ihren Strukturen, in den Kriterien und den Problemdomänen. Im Gebiet der künstlichen Intelligenz ist es jedoch gebräuchlich, zwei breite Klassen von Suchphilosophien zu unterscheiden, nämlich "Breite- Zuerst"-Suchen und "Tiefe-Zuerst"-Suchen.

Schritt 610

Die 9 unterschiedlichen Kandidatenwege auf dem Niveau -1, die im Schritt 604 erzeugt und durch die Niveaus 2 bis 5 (d. h. Schritt 605 bis 609) verlängert wurden, bilden 9 Kandidaten-Codevektoren A_k (vergl. 505 in Fig. 5).

Der Zweck des Schrittes 610 besteht darin, die 9 Kandi daten-Codevektoren A_k zu vergleichen und den besten ent sprechend dem Auswahlkriterium, welches dem letzten Niveau zugeordnet ist, nämlich Q_k(10) auszuwählen.

Es folgt ein drittes Ausführungsbeispiel für die "Tiefe- Zuerst"-Codebuchsuche, genannt "Suchverfahren Nr. 3". Hier durch soll ein Fall illustriert werden, in dem mehr als ein Impuls dieselbe Position einnehmen können.

Suchverfahren Nr. 3 10 Impulse oder weniger Algebraisches Codebuch

L = 40; N = 10
Anzahl unterschiedlicher Impulse 10
Summe von zwei ISPP (40, 5)
i.e.: (L₁ = L₂ = . . . L₅ = 8; L₆ = L₇ = . . . L₁0 = 8)

Suchvorgang

Regel R5

Beachte, daß zwei Impulse dieselbe Position einnehmen können; deshalb addieren sich ihre Amplituden, was einen Impuls mit doppelter Amplitude ergibt. Regel R5 bestimmt die Art, in welcher die ersten zwei Impulspositionen ausgewählt werden, um zum Satz von Wegkandidaten auf dem Niveau -1 zu kommen. Die

= 50 Knotenpunkte der Kandidatenwege auf dem Niveau -1 entsprechen einem Impuls mit doppelter Amplitude an jeder Position, welche B_p in den 5 unterschiedlichen "Tracks" maximiert, und allen Kombinationen von 2 Impulspositionen aus dem Pool von 10 Impulspositionen, die dadurch ausgewählt werden, daß diejenigen beiden Positionen herausgegriffen werden, welche B_p in jedem der 5 unterschiedlichen "Tracks" maximieren.

Regel R6: ähnlich der Regel R4

Oben wurden im Detail bevorzugte Ausführungsbeispiele der vorliegenden Erfindung beschrieben. Diese Ausführungs beispiele können jedoch innerhalb des Umfanges der anlie genden Ansprüche nach Gutdünken modifiziert werden, ohne von dem Grundgedanken der Erfindung abzuweichen. Die Er findung ist auch nicht auf die Behandlung von Sprachsig nalen beschränkt; andere Arten von Geräusch- oder Klang signalen, beispielsweise Audiosignale, können in gleicher Weise verarbeitet werden. Derartige Modifikationen, welche das Grundprinzip beibehalten, liegen offensichtlich inner halb des Umfanges der vorliegenden Erfindung.

Claims

1. Verfahren zur Durchführung einer "Tiefe-Zuerst"-Suche in einem Codebuch zur Codierung eines Geräusch- bzw. Klangsignales, bei welchem:
das Codebuch einen Satz von Codevektoren A_k umfaßt, die jeweils eine Vielzahl unterschiedlicher Positionen p de finieren und N Nicht-Null-Amplituden-Impulse umfassen, von denen jeder einer vorherbestimmten gültigen Position p des Codevektors zuordenbar ist;
wobei die "Tiefe-Zuerst"-Suche eine Baumstruktur benutzt, die eine Anzahl M geordneter Niveaus definiert, von denen jedes Niveau m einer vorherbestimmten Anzahl N_m von Nicht-Null-Amplituden-Impulsen, N_m1, zugeordnet ist, wobei die Summe der vorherbestimmten Zahlen, die allen M Niveaus zugeordnet sind, gleich der Zahl N der Nicht-Null- Amplituden-Impulse ist, die sich in den Codevektoren befinden, und wobei ferner jedes Niveau m der Baumstruktur außerdem einem Weg-Aufbau-Vorgang zugeordnet ist mit einer vorgegebenen Impulsordnungsregel und mit einem vorgegebenen Auswahlkriterium;
wobei das "Tiefe-Zuerst"-Codebuch-Suchverfahren die folgenden Schritte umfaßt:

- in einem Niveau 1 der Baustruktur besteht der zugeordnete Weg-Aufbau-Vorgang in folgendem:
eine Zahl N₁ der N-Nicht-Null-Amplituden-Impulse wird entsprechend der zugeordneten Impulsordnungsregel gewählt;
mindestens eine der gültigen Positionen p der N₁ Nicht- Null-Amplituden-Impulse wird entsprechend dem zugeordne ten Auswahlkriterium so gewählt, daß mindestens ein Kandidatenweg auf dem Niveau -1 definiert wird;
- in einem Niveau m der Baumstruktur definiert der zuge ordnete Weg-Aufbau-Vorgang rekursiv einen Kandidatenweg auf dem Niveau -m, indem ein Kandidatenweg auf dem Niveau -(m-1) durch die folgenden Unterschritte verlängert wird:
N_m der Nicht-Null-Amplituden-Impulse, die nicht schon zuvor im Verlaufe des Aufbaues des Weges auf dem Niveau -(m-1) ausgewählt wurden, werden entsprechend der zuge ordneten Impulsordnungsregel gewählt;
mindestens eine der gültigen Positionen p der N_m Nicht- Null-Amplituden-Impulse wird entsprechend dem zugeord neten Auswahlkriterium so ausgewählt, daß mindestens ein Kandidatenweg auf dem Niveau -m gebildet wird;
wobei ein Kandidatenweg auf dem Niveau -M, der auf dem Niveau -1 entstanden ist und bei den Weg-Aufbau-Vor gängen, welche darauffolgenden Niveaus der Baumstruk tur zugeordnet sind, verlängert wurde, die entsprechen den Positionen p der N Nicht-Null-Amplituden-Impulse eines Codevektors bestimmt und auf diese Weise einen Kandidaten-Codevektor A_k definiert.

2. Verfahren zur Durchführung einer "Tiefe-Zuerst"-Suche in einem Codebuch zur Codierung eines Geräusch- bzw. Klangsignals, bei dem:
das Codebuch einen Satz von Codevektoren A_k umfaßt, die jeweils eine Mehrzahl unterschiedlicher Positionen p de finieren und N Nicht-Null-Amplituden-Impulse umfassen, von denen jeder vorherbestimmten gültigen Positionen p des Codevektors zuordenbar ist;
wobei die "Tiefe-Zuerst"-Suche Gebrauch macht von (a) einer Unterteilung der N Nicht-Null-Amplituden-Impulse in eine Anzahl M von Untersätzen, von denen jeder mindestens einen Nicht-Null-Amplituden-Impuls umfaßt, und (b) einer Baumstruktur, welche Knotenpunkte enthält, welche für die gültigen Positionen p der N Nicht-Null-Amplituden-Impulse repräsentativ sind und eine Mehrzahl von Suchniveaus definieren, von denen jedes einem der M Untersätze zugeord net ist, und wobei jedes Suchniveau außerdem einer vorge gebenen Impulsordnungsregel und einem vorgegebenen Selek tionskriterium zugeordnet ist;
wobei das "Tiefe-Zuerst"-Codebuch-Suchverfahren folgende Schritte umfaßt:

3. "Tiefe-Zuerst"-Codebuch-Suchverfahren nach Anspruch 2, bei welchem der mindestens eine Weg eine Mehrzahl von Wegen umfaßt und bei welchem die Suchniveaus der Baum struktur ein letztes Suchniveau enthalten und das Verfahren im letzten Suchniveau der Baumstruktur den Schritt umfaßt, daß, entsprechend dem zugeordneten Auswahlkriterium, einer der Kandidaten-Vektoren A_k ausgewählt wird, der von den Wegen definiert wird, zur Codierung des Geräusch- bzw. Klangsignales.

4. "Tiefe-Zuerst"-Codebuch-Suchverfahren nach Anspruch 2, welches außerdem den Schritt umfaßt, daß die vor herbestimmten gültigen Positionen p der N Nicht-Null- Amplituden-Impulse in Übereinstimmung mit mindestens einem verzahnten ("interleaved") Einzel-Impuls-Permutationsdesign abgeleitet werden.

5. "Tiefe-Zuerst"-Codebuch-Suchverfahren nach Anspruch 2, bei welchem der Auswahlschritt in jedem der nach folgenden Suchniveaus der Baumstruktur umfaßt:
das Errechnen eines vorgegebenen mathematischen Verhält nisses für jeden Weg, der durch die Impulsposition(en) p definiert ist, der oder die in dem oder den früheren Suchniveau(s) ausgewählt wurde(n) und durch jede gültige Position p von dem mindestens einen Impuls des Untersatzes, der dem nachfolgenden Suchniveau zugeordnet ist, verlängert wurde(n); und
das Beibehalten des verlängerten Weges, der durch die Impulspositionen p definiert ist, welche das vorgegebene Verhältnis maximieren.

6. "Tiefe-Zuerst"-Codebuch-Suchverfahren nach Anspruch 2, bei welchem an dem ersten Suchniveau der Baumstruk tur die Wähl- und Auswahlschritte in folgender Weise ausge führt werden:
Errechnen eines Impulspositions-Wahrscheinlichkeits schätzvektors bezüglich des Geräusch- bzw. Klangsignales; und
Auswahl des mindestens einen Nicht-Null-Amplituden-Impuls des zugeordneten Untersatzes und der mindestens einen gültigen Position p hiervon entsprechend dem Impuls positions -Wahrscheinlichkeitsschätzvektor.

7. "Tiefe-Zuerst"-Codebuch-Suchverfahren nach Anspruch 6, bei welchem der Schritt zur Errechnung des Impuls positions-Wahrscheinlichkeitsschätzvektors folgende Schritte umfaßt:
das Geräusch- bzw. Klangsignal wird so verarbeitet, daß ein Zielsignal X, ein rückwärts gefiltertes Zielsignal D und ein Höhen-("Pitch"-)entferntes Restsignal R′ erzeugt werden; und
der Impulspositions-Wahrscheinlichkeitsschätzvektor B wird auf mindestens eines der nachfolgenden Signale hin errechnet: Zielsignal X, rückwärts gefiltertes Zielsignal D und Höhen-entferntes Restsignal R′.

8. "Tiefe-Zuerst"-Codebuch-Suchverfahren nach Anspruch 7, bei welchem der Schritt der Errechnung des Impuls positions-Wahrscheinlichkeitsschätzvektors B auf minde stens eines der nachfolgenden Signale hin: Zielsignal X, rückwärts gefiltertes Zielsignal D und Höhen-entferntes Restsignal R′, umfaßt:
das Addieren des rückwärts gefiltertes Zielsignales D in normalisierter Form: zu dem Höhen-entfernten Restsignal R′ in normalisierter Form: wodurch ein Impulspositions-Wahrscheinlichkeitsschätz vektor B der Form erhalten wird, worin ß eine feste Konstante ist.

9. "Tiefe-Zuerst"-Codebuch-Suchverfahren nach Anspruch 8, bei welchem β eine feste Konstante mit einem Wert zwischen 0 und 1 ist.

10. "Tiefe-Zuerst"-Codebuch-Suchverfahren nach Anspruch 9, bei welchem ß eine feste Konstante ist, die den Wert 1/2 aufweist.

11. "Tiefe-Zuerst"-Codebuch-Suchverfahren nach Anspruch 2, bei welchem die N Nicht-Null-Amplituden-Impulse entsprechende Indices aufweisen und bei welchem in jedem der nachfolgenden Suchniveaus der Baumstruktur der Schritt des Wählens von mindestens einem der Nicht-Null-Amplituden- Impulse, die nicht schon zuvor gewählt wurden, entspre chend der zugeordneten Impulsordnungsfunktion das Auslegen der Indices der zuvor nicht gewählten Impulse auf einem Kreis und das Wählen des mindestens einen Nicht-Null- Amplituden-Impulses entsprechend einer Folge der Indices im Uhrzeigersinn, wobei rechts von dem letzten Nicht-Null- Amplituden-Impuls begonnen wird, welcher in dem früheren Suchniveau der Baumstruktur ausgewählt wurde.

12. Vorrichtung zur Durchführung einer "Tiefe-Zuerst"- Suche in einem Codebuch zur Codierung eines Geräusch- oder Klangsignals, bei der:
das Codebuch einen Satz von Codevektoren A_k umfaßt, die jeweils eine Mehrzahl unterschiedlicher Positionen p de finieren und N Nicht-Null-Amplituden-Impulse umfassen, von denen jeder vorherbestimmten gültigen Positionen p des Codevektors zuordenbar ist;
die "Tiefe-Zuerst"-Suche Gebrauch macht von (a) der Unterteilung der N Nicht-Null-Amplituden-Impulse in eine Anzahl M von Untersätzen, von denen jeder mindestens einen Nicht-Null-Amplituden-Impuls umfaßt, und (b) einer Baum struktur, welche Knotenpunkte enthält, welche für die gültigen Positionen p der N Nicht-Null-Amplituden-Impulse repräsentativ sind und eine Mehrzahl von Suchniveaus definieren, von denen jedes einem der M Untersätze zugeord net ist und außerdem einer vorgegebenen Pulsordnungsregel und einem vorgegebenen Auswahlkriterium zugeordnet ist;
wobei die "Tiefe-Zuerst"-Codebuch-Suchvorrichtung umfaßt:

- für ein erstes Suchniveau der Baumstruktur:
eine erste Einrichtung zum Wählen von mindestens einem der N Nicht-Null-Amplituden-Impulse entsprechend der zugeordneten Impulsordnungsregel zur Bildung des zugeord neten Untersatzes;
eine erste Einrichtung zur Auswahl von mindestens einer der gültigen Positionen p des mindestens einen Nicht- Null-Amplituden-Impulses entsprechend dem zugeordneten Auswahlkriterium zum Definieren von mindestens einem Weg durch die Knotenpunkte der Baumstruktur;
- für jedes darauffolgende Suchniveau der Baumstruktur:
eine zweite Einrichtung zum Wählen von mindesten einem der Nicht-Null-Amplituden-Impulse, die nicht zuvor schon gewählt wurde, entsprechend der zugeordneten Impuls ordnungsfunktion zur Bildung des zugeordneten Untersatzes;
eine zweite Einrichtung zur Auswahl in dem darauffolgen den Suchniveau von mindestens einer der gültigen Positio nen p des mindestens einen Nicht-Null-Amplituden-Impulses des zugeordneten Untersatzes entsprechend dem zugeord neten Auswahlkriterium, wodurch der mindestens eine Weg durch die Knotenpunkte der Baumstruktur verlängert wird,

13. "Tiefe-Zuerst"-Codebuch-Suchvorrichtung nach Anspruch 12, bei welcher der mindestens eine Weg eine Mehrzahl von Wegen umfaßt, die Suchniveaus der Baumstruktur ein letztes Suchniveau enthalten und die Vorrichtung eine Einrichtung zur Auswahl von mindestens einem der Kandidaten- Codevektoren A_k, die von diesen Wegen definiert sind, in dem letzten Suchniveau der Baumstruktur entspre chend dem zugeordneten Auswahlkriterium für die Codierung des Geräusch- bzw. Klangsignals umfaßt.

14. "Tiefe-Zuerst"-Codebuch-Suchvorrichtung nach Anspruch 12, welche außerdem eine Einrichtung umfaßt, welche die vorherbestimmten gültigen Positionen p der N Nicht- Null-Amplituden-Impulse entsprechend mindestens einem verzahnten ("interleaved") Einfach-Impuls-Permutations design ableitet.

15. "Tiefe-zuerst"-Codebuch-Suchvorrichtung nach Anspruch 12, bei welcher die zweite Auswahleinrichtung umfaßt:
eine Einrichtung, welche ein vorgegebenes mathematisches Verhältnis für jeden Weg errechnet, der durch die Impuls position(en) p, der bzw. die in dem bzw. den früheren Suchniveau(s) ausgewählt wurden(n), definiert und durch jede gültige Position p des mindestens einen Impulses des Untersatzes, welcher dem darauffolgenden Suchniveau zugeordnet ist, verlängert wurde; und
eine Einrichtung, welche den verlängerten Weg, der durch die Impulspositionen p, welche das vorgegebene Verhältnis maximieren, definiert ist, beibehält.

16. "Tiefe-Zuerst"-Codebuch-Suchvorrichtung nach Anspruch 12, bei welcher die erste Wähleinrichtung und die erste Auswahleinrichtung umfassen:
eine Einrichtung zur Errechnung eines Impulspositions- Wahrscheinlichkeitsschätzvektors in Bezug auf das Geräusch- bzw. Klangsignal; und
eine Einrichtung zur Auswahl des mindestens einen Nicht- Null-Amplituden-Impulses des zugeordneten Untersatzes und der mindestens einen gültigen Position p hiervon entspre chend dem Impulspositions-Wahrscheinlichkeitsschätzvek tor.

17. "Tiefe-Zuerst"-Codebuch-Suchvorrichtung nach Anspruch 16, bei welcher die Einrichtung zur Errechnung des Impulspositions-Wahrscheinlichkeitsschätzvektors umfaßt:
eine Einrichtung zur Verarbeitung des Geräusch- bzw. Klang signales derart, daß ein Zielsignal X, ein rückwärts ge filtertes Zielsignal D und ein Höhen-("Pitch"-)-entferntes Restsignal R′ erzeugt werden; und
eine Einrichtung, welche den Impulspositions-Wahrschein lichkeitsschätzvektor B auf mindestens eines der nach folgenden Signale hin errechnet: Zielsignal X, rückwärts gefiltertes Zielsignal D und Höhen-entferntes Restsignal R′.

18. "Tiefe-Zuerst"-Codebuch-Suchvorrichtung nach Anspruch 17, bei welcher die Einrichtung zur Errechnung des Impulspositions-Wahrscheinlichkeitsschätzvektors B auf mindestens eines der nachfolgenden Signale hin: Zielsignal X, rückwärts gefiltertes Signal D und Höhen-entferntes Restsignal R′, umfaßt:
eine Einrichtung, welche das rückwärts gefilterte Ziel signal D in normalisierter Form: zu dem Höhen-entfernten Restsignal R′ in normalisierter Form: addiert, wodurch ein Impulspositions-Wahrscheinlichkeits schätzvektor B der Form: erhalten wird, worin β eine feste Konstante ist.

19. "Tiefe-Zuerst" -Codebuch-Suchvorrichtung nach Anspruch 18, bei welcher β eine feste Konstante mit einem Wert zwischen 0 und 1 ist.

20. "Tiefe-Zuerst"-Codebuch-Suchvorrichtung nach Anspruch 19, bei welcher β eine feste Konstante mit dem Wert 1/2 ist.

21. "Tiefe-Zuerst"-Codebuch-Suchvorrichtung nach Anspruch 12, bei welcher die N Nicht-Null-Amplituden-Impulse entsprechende Indices aufweisen und die zweite Wählein richtung umfaßt:
eine Einrichtung zum Auslegen der Indices der zuvor nicht gewählten Impulse auf einem Kreis; und
eine Einrichtung zum Wählen des mindestens einen Nicht- Null-Amplituden-Impulses entsprechend einer im Uhrzeiger sinn laufenden Folge der Indices, beginnend rechts von dem letzten Nicht-Null-Amplituden-Impuls, der in dem frü heren Suchniveau der Baumstruktur ausgewählt wurde.

22. Zellulares Kommunikationssystem zur Bedienung eines großen geografischen Gebietes, welches in eine Mehr zahl von Zellen unterteilt ist, mit:
mobilen Transmitter/Empfänger-Einheiten;
zellularen Basisstationen, die jeweils in den Zellen an geordnet sind;
Einrichtungen zur Steuerung der Kommunikation zwischen den zellularen Basisstationen;
einem bidirektionen Funk-Kommunikations-Untersystem zwischen jeder mobilen Einheit, die in einer Zelle angeord net ist, und der zellularen Basisstation dieser einen Zelle, welches sowohl in der mobilen Einheit als auch in der zellularen Basisstation umfaßt: (a) einen Sender, der eine Einrichtung zur Codierung eines Sprachsignales und eine Einrichtung zum Senden des codierten Sprachsignales enthält; und (b) einen Empfänger, der eine Einrichtung zum Empfang eines gesendeten codierten Sprachsignales und eine Einrichtung zur Decodierung des empfangenen codierten Sprachsignales enthält;
wobei die Codiereinrichtung für das Sprachsignal eine Vorrichtung umfaßt, welche eine "Tiefe-Zuerst"-Suche in einem Codebuch für die Codierung des Sprachsignales durchführt, bei welcher
das Codebuch einen Satz von Codevektoren A_k umfaßt, die jeweils eine Mehrzahl von unterschiedlichen Positionen p definieren und N Nicht-Null-Amplituden-Impulse umfassen, die jeweils bestimmten gültigen Positionen p des Codevek tors zuordenbar sind;
die "Tiefe-Zuerst"-Codebuch-Suche Gebrauch macht von: (a) einer Unterteilung der N Nicht-Null-Amplituden-Impulse in eine Anzahl M von Untersätzen, die jeweils mindestens einen Nicht-Null-Amplituden-Impuls umfassen; und (b) einer Baum struktur, welche Knotenpunkte enthält, die für die gültigen Positionen p der N Nicht-Null-Amplituden-Impulse repräsen tativ sind und eine Mehrzahl von Suchniveaus definieren, die jeweils einem der M Untersätze und außerdem einer vorgegebenen Impuls-Ordnungsregel und einem vorgegebenen Auswahlkriterium zugeordnet sind;
wobei die "Tiefe-Zuerst"-Codebuch-Suchvorrichtung umfaßt:

- für ein erstes Suchniveau der Baumstruktur:
eine erste Einrichtung zum Wählen von mindestens einem der N Nicht-Null-Amplituden-Impulse entsprechend der zugeordneten Impulsordnungsregel zur Bildung des zugeord neten Untersatzes;
eine erste Einrichtung zur Auswahl von mindestens einer der gültigen Positionen p des mindestens einen Nicht- Null-Amplituden-Impulses entsprechend dem zugeordneten Auswahlkriterium zum Definieren von mindestens einem Weg durch die Knotenpunkte der Baumstruktur;
- für jedes darauffolgende Suchniveau der Baumstruktur:
eine zweite Einrichtung zum Wählen von mindestens einem der Nicht-Null-Amplituden-Impulse, die nicht schon zuvor gewählt wurden, entsprechend der zugeordneten Impuls- Ordnungsregel zur Bildung des zugeordneten Untersatzes; und
eine zweite Einrichtung zur Auswahl von mindestens einer der gültige Positionen p des mindestens einen Nicht-Null- Amplituden-Impulses des zugeordneten Untersatzes in dem darauffolgenden Suchniveau entsprechend dem zuge ordneten Auswahlkriterium, wodurch der mindestens eine Weg durch die Knotenpunkte der Baumstruktur verlängert wird;

23. Zellulares Kommunikationssystem nach Anspruch 22, bei welchem der mindestens eine Weg eine Mehrzahl von Wegen umfaßt, die Suchniveaus der Baumstruktur ein letztes Suchniveau enthalten und die Vorrichtung eine Einrichtung zur Auswahl eines der Kandidaten-Codevektoren A_k, die durch die Wege definiert sind, in dem letzten Suchniveau der Baumstruktur entsprechend dem zugeordneten Auswahlkriterium zur Codierung des Geräusch- bzw. Klang signales umfaßt.

24. Zellulares Kommunikationssystem nach Anspruch 22, welches außerdem eine Einrichtung enthält, welche die vorherbestimmten gültigen Positionen p der N Nicht- Null-Amplituden-Impulse entsprechend mindestens einem verzahnten ("interleaved") Einfach-Impuls-Permutationsde sign ableitet.

25. Zellulares Kommunikationssystem nach Anspruch 22, bei welchem die zweite Auswahleinrichtung umfaßt:
eine Einrichtung zum Errechnen eines vorgegebenen mathe matischen Verhältnisses für jeden Weg, der durch die Im puls-Position(en) p definiert ist, der bzw. die in dem bzw. den früheren Suchniveau(s) definiert und durch jede gültige Position p des mindestens einen Impulses des Unter satzes, welcher dem darauffolgenden Suchniveau zugeordnet ist, verlängert wurde(n); und
eine Einrichtung, welche den verlängerten Weg, der durch die Impulspositionen p, welche das vorgegebene Verhältnis maximieren, definiert ist, beibehält.

26. Zellulares Kommunikationssystem nach Anspruch 22, bei welchem die erste Wähleinrichtung und die erste Auswahleinrichtung umfassen:
eine Einrichtung zum Errechnen eines Impulspositions- Wahrscheinlichkeitsschätzvektors in Bezug auf das Geräusch- bzw. Klangsignal; und
eine Einrichtung zur Auswahl des mindestens einen Nicht- Null-Amplituden-Impulses des zugeordneten Untersatzes und der mindestens einen gültigen Position p hiervon entsprechend dem Impulspositions-Wahrscheinlichkeits schätzvektor.

27. Zellulares Kommunikationssystem nach Anspruch 26, bei welchem die Einrichtung zum Errechnen des Impuls positions-Wahrscheinlichkeitsschätzvektors umfaßt:
eine Einrichtung, welche das Geräusch- bzw. Klangsignal so verarbeitet, daß ein Zielsignal X, ein rückwärts ge filtertes Zielsignal D und ein Höhen-("Pitch"-)-entferntes Restsignal R′ erzeugt werden; und
eine Einrichtung, welche den Impulspositions-Wahrschein lichkeitsschätzvektor B auf mindestens eines der nach folgenden Signale hin errechnet: Zielsignal X, rückwärts gefiltertes Zielsignal D und Höhen-entferntes Restsignal R′.

28. Zellulares Kommunikationssystem nach Anspruch 27, bei welchem die Einrichtung zum Errechnen des Impuls positions-Wahrscheinlichkeitsschätzvektors B auf mindes tens eines der nachfolgenden Signale hin: Zielsignal X, rückwärts gefiltertes Zielsignal D und Höhen-entferntes Restsignal R′, umfaßt:
eine Einrichtung, welche das rückwärts gefilterte Ziel signal D in normalisierter Form zu dem Höhen-entfernten Restsignal R′ in normalisierter Form addiert, wodurch ein Amplituden-Schätzvektor B der Form erhalten wird, worin β eine feste Konstante ist.

29. Zellulares Kommunikationssystem nach Anspruch 28, bei welchem β eine feste Konstante mit einem Wert zwischen 0 und 1 ist.

30. Zellulares Kommunikationssystem nach Anspruch 29, bei welchem β eine feste Konstante mit dem Wert 1/2 ist.

31. Zellulares Kommunikationssystem nach Anspruch 22, bei welchem die N Nicht-Null-Amplituden-Impulse ent sprechende Indices aufweisen und bei welchem die zweite Wähleinrichtung umfaßt:
eine Einrichtung, welche die Indices der nicht schon zuvor gewählten Impulse auf einem Kreis auslegt; und
eine Einrichtung, welche den mindestens einen Nicht-Null- Amplituden-Impuls entsprechend einer im Uhrzeigersinn verlaufenden Folge von Indices wählt, beginnend rechts von dem letzten Nicht-Null-Amplituden-Impuls, der in dem vorhergehenden Suchniveau der Baumstruktur gewählt wurde.