DE69214969T2

DE69214969T2 - Verfahren und Vorrichtung zur Erzeugung von Hilfsinformationen zur Ausführung einer Suche in einem Kodebuch mit geringer Dichte

Info

Publication number: DE69214969T2
Application number: DE69214969T
Authority: DE
Inventors: Kumar Swaminathan
Original assignee: AT&T Corp
Current assignee: AT&T Corp
Priority date: 1991-01-28
Filing date: 1992-01-17
Publication date: 1997-03-27
Anticipated expiration: 2012-01-18
Also published as: EP0497479A1; DE69214969D1; EP0497479B1; US5195137A; DK0497479T3

Description

Erfindungsgebiet

Die vorliegende Erfindung betrifft Codetabellen- Durchsuchungsverfahren und insbesondere das Durchsuchen von im Speicher gespeicherten Codetabellen, die für die Sprachverarbeitung in Fernsprechkommunikationssystemen benutzt werden.

Stand der Technik

Bei der Verarbeitung von Sprache für Fernsprechkommunikationssysteme einschließlich digitaler Mobilfunksysteme gewinnt die digitale Übertragung an Bedeutung. Analoge Sprachsignale werden zur Übertragung in digitale Daten umgewandelt und am Abschlußende der Übertragung wieder in analoge Sprache rekonstruiert. Die digitale Sprachverarbeitung hat viele Erfordernisse für Kompromisse, bei denen Sprachqualität gegen verfügbaren Speicher, Verarbeitungsgeschwindigkeit und Bandbreiteerfordernisse abgewogen werden muß.
Aufgrund von wachsendem Bedarf und dem Übergang zur digitalen Übertragung hat sich die erforderliche Bandbreite für einen Fernsprechübertragungskanal bedeutend vergrößert. Dies hat zur Entwicklung von digitalen Datenverarbeitungsverfahren zur Verringerung der für eine bestimmte Ebene von Teilnehmerkapazität für einen Fernsprechübertragungskanal erforderlichen Bandbreite geführt.
Die Erhöhung der Anzahl von Kanälen für eine bestimmte Bandbreite wurde durch Anwendung von Verfahren zur Verringerung der erforderlichen Bitrate zur Aufnahme einer gegebenen Kapazität erreicht. Zu diesen Verfahren gehören viele Datenkomprimierungsmethoden zur Verringerung der Anzahl von Bit, die zur Angabe eines bestimmten Analogsignals erforderlich sind. Beispielsweise würde die einfache Umwandlung eines analogen Sprachsignals in digitale Form eine sehr große Bandbreite für die Übertragung erfordern, wodurch eine solche Übertragung wahrscheinlich unwirtschaftlich werden würde. Durch Komprimierung der digitalen Daten kann die erforderliche Übertragungsbandbreite bedeutend verringert werden.
Um die gewünschte Datenkomprimierung zur Verringerung der für die Übertragung erforderlichen Bandbreite zu erreichen, sind viele verschiedene Codierverfahren ausgearbeitet worden. Viele dieser Verfahren erfordern die Umwandlung eines digital codierten Signals in irgendein voreingestelltes quantisiertes Signal. Ein solches Signal wird dadurch abgeleitet, daß ein anfangs digitalisiertes Signal mit einer begrenzten Menge vorausgewählter digital codierter Stufen verglichen wird, die in einer einem Speicher zugewiesenen Codetabelle enthalten sind. Das anfangs digitalisierte Signal wird mit jedem Codetabelleneintrag verglichen und der das anfangs digitalisierte Signal am besten darstellende Codetabelleneintrag wird zur Übertragung bzw. zur Weiterverarbeitung vor einer nachfolgenden Übertragung ausgewählt.
Eine Suche nach einem paarigen gespeicherten Code unter Verwendung eines elementweisen Vergleichs ist zeitaufwendig, wenn die Codetabelle groß ist, und ist daher nicht für Sprachübertragungssysteme, die in Echtzeit arbeiten, geeignet. Die Verwendung kleiner leicht durchsuchter Codetabellen ist unannehmbar, da damit nicht genügend Informationen bereitgestellt werden, um das ursprüngliche Analogsignal genau wiederzugeben.
Viele alternative Codetabellensuchverfahren sind entwickelt worden, um das Verfahren zu beschleunigen und Durchsuchungen in der Echtbetriebszeit des Sprachverarbeitungssystems zu erlauben. Viele dieser Verfahren nutzen bekannte Eigenschaften von Sprachsignalen und bekannte Eigenschaften von digitalen Codes. Zu diesen Verfahren gehörten die Verfahren des Standes der Technik der sorgfältigen Vorauswahl der Codetabelleneinträge angesichts der erwarteten Eigenschaften des Sprachsignals zur Verbesserung der nachfolgenden Suchverfahren und verschiedene Verzerrungsmeßverfahren zum Messen erwarteter Verzerrungen zwischen dem eigentlichen und dem codierten Signal.
In EP-A-0 307 122 sind Sprachverarbeitungsschaltungen offenbart, die Analogsprache annehmen und sie mit einem Analog-Digital-Wandler in Digitalsprache umwandeln. Die Digitalsprache wird unter Verwendung eines Formats mit dünnbesetzter Codetabelle als Vektorgröße codiert, wobei jeder Eintrag durch ein Indexglied dargestellt ist. Eine Suchschaltung wählt aus der dünnbesetzten Codetabelle einen Vektor aus, der die Zielvektorgröße des Digitalsprachsignals am genauesten darstellt, indem sie einen Entfernungswert zwischen dem Zielvektor und dem zufallsmäßigen Vektor der Codetabelle bestimmt.
In einem Artikel mit dem Titel "A Systolic Vector Quantisation Processor for Real-time Speech Coding" (Ein systolischer Vektorquantisierungsprozessor für Echtzeit- Sprachcodierung) in ICASSP '86 (7. April 1988), Seiten 2143-2146 ist ein VLSI-Vektorguantisierungsprozessor offenbart. Vorkehrungen sind getroffen zum Berechnen von Verzerrungsmaßen und zum Ausdrücken dieser Maße als inneres Vektorprodukt.

Darstellung der Erfindung

Die Erfindung entspricht den Ausführungen in den unabhangigen Ansprüchen.
In vielen Anwendungen mit der Codierung und Verarbeitung von Sprachsignalen ist die entsprechende geltende Codetabelle eine, die als dünnbesetzte Codetabelle bezeichnet werden kann. Das heißt, die meisten Elemente in der Codetabelle haben einen Wert von Null. Die Durchsuche einer solchen dünnbesetzten Codetabelle wird gemäß der vorliegenden Erfindung durch die Erzeugung von Hilfsinformationen, die die dünne Besetzung der Codetabelle definieren, und durch Verwendung dieser Informationen zur Unterstützung und Beschleunigung von Durchsuchungen der Codetabelle beschleunigt.
In einem bestimmten Suchverfahren wird die Berechnung der Entfernung zwischen einem Zielvektor und einem gespeicherten Codetabellenvektor durch Verwendung einer aus Energiegliedern und Korrelationsgliedern der Codetabelleneinträge abgeleiteten Verzerrungsmetrik verbessert. Berechnung dieser Energie- und Korrelationsglieder wird nach dem Grundsatz der Erfindung durch Ausnutzung der dünnen Besetzung der Codetabelleneinträge beschleunigt. Die Nicht-Null- Elemente (NZE - non-zero elements) der dünnbesetzten Codetabelle werden jeweils gekennzeichnet und werden durch ihren Relativzeiger von einem Bezugspunkt definiert. Diese Posten werden zur Beschleunigung der Codetabellendurchsuchung verwendet.
Bei der Sprachcodierung, Anwendungen mit niedrigratigen CELP-Codec, sind die Codetabellen typischerweise dünn besetzt und überlappen einander und benutzen eine symmetrische Toeplitz - Spektralgewichtungsmatrix zur Berechnung des Verzerrungsgliedes fur jeden Codetabellenvektor. Hilfsinformationen zur Unterstützung dieser Berechnungen können durch Ausnutzung dieser hinzugefügten bestehenden Zustände bedeutend verbessert werden.

Kurze Beschreibung der Zeichnung

In der Zeichnung ist:
Figur 1 ein Blockschaltbild von Sprachübertragungs- und Empfangsschaltungen für eine Sende-/Empfängereinheit in einem digitalen Mobilfunk- Fernsprechsystem;
Figur 2 ein Schaltschema eines Sprachverarbeitungsmoduls für ein digitales Mobilfunk- Fernsprechkommunikations system;
Figur 3 eine Wellenform, die zeigt, wie die Sprachcodierung auf codierte Rahmen von Sprachsignalen angewandt wird;
Figur 4 ein Flußdiagramm der Codierung von Sprache im Sprachverarbeitungsmodul der Figur 1;
Figur 5 ein Flußdiagramm der Decodierung der Sprache, die durch den Vorgang der Figur 4 codiert worden ist;
Figuren 6-12 Flußdiagramme einer Durchsuchung einer im Vorgang der Figur 4 vorkommenden stochastischen Codetabelle.

Ausführliche Beschreibung

In Figur 1 ist ein typischer Funksender und -empfänger dargestellt, die in zellularer Funkkommunikation benutzt werden und Sprachcodier- und -decodiereinrichtun gen aufweisen. Im Sendeteil wird Analogsprache über die Eingangsklemme 100 an den Analog-Digital-Codec 101 angelegt. Die digitalisierte Sprache wird im Sprachcodierer 102 codiert und an den Kanalcodierer 103 angelegt. Das Signal wird im Modulator 104 moduliert und an den Funksender 105 angelegt, der ein HF-Signal an den Verstärker 106 anlegt. Der Ausgang des Verstärkers 106 ist zur Funkübertragung an die Antenne 107 angekoppelt.
Die Antenne 117 empfängt übertragene Funksignale und legt sie über den Verstärker 116 an einen Funkempfänger 115 an. Dieses Funksignal wird im Demodulator 114 demoduliert und im Kanaldecodierer 113 kanaldecodiert. Das Sprachsignal wird im Sprachdecodierer 112 decodiert und im Digital-Analog-Codec 111 in ein Analogsprachsignal umgewandelt. Das Analogsprachsignal wird an der Ausgangsklemme 110 abgegeben.
In Figur 2 ist ein Blockschaltbild einer Sprachcodiereinrichtung offenbart, die zur Verwendung als Sprachcodierer in einem digitalen Funktelekommunikationssystem geeignet ist. Diese Sprachcodiereinrichtung ist ein CELP- (code excited linear predictive)Sprachcodierer, bei dem ankommende Analogsprachsignalabtastwerte in eine digitale Vektorform umgewandelt werden. CELP-Codierung bietet gute Sprachqualität bei niedrigen Bitraten. Der digitale Vektor des ankommenden Sprachabtastwertes wird mit einer in einer Codetabelle oder digitalen Speichervorrichtung gespeicherten Menge von Vektoren verglichen. Der dem digitalen Vektor des Sprachabtastwertes am genauesten im Wert entsprechende abgespeicherte Vektor wird ausgewählt und eine mit dem gespeicherten Vektor verbundene Indexnummer (eine Adresse) ist das übertragene Signal. Die Indexnummer wird zur Auswahl eines gespeicherten Vektors in einer Codetabelle bei einem Empfänger benutzt, aus dem das ursprüngliche Sprachsignal wiederherzustellen ist.
In der Einrichtung der Figur 2 wird das ankommende Sprachsignal über die Eingangsleitung 201 an eine Summierschaltung 202 angelegt, die eine Differenz zwischen einem synthetisierten Sprachsignal auf der Leitung 204 und dem ankommenden Sprachsignal auf der Leitung 201 bestimmt. Das sich ergebende Differenzsignal wird an ein Frequenz- oder Spektralgewichtungsfilter 207 angelegt, das als Reaktion auf an dieses als Eingabe angelegte Filterparameter die Erzeugung eines gewichteten Spektrumfehlersignals bewirkt, das eine korrigierte Differenz zwischen der Eingangssprache und dem synthetisierten Sprachsignal darstellt.
Die Leistung im Spektrumfehlersignal wird in der Energieberechnungsvorrichtung 205 gemessen, deren Energiesignalausgabe zur Durchsuche einer stochastischen Codetabelle 210 benutzt wird, so daß die Signalenergie auf einem Mindestwert gehalten wird. Die stochastische Codetabelle ist normalerweise durch Zufallsvektoren belegt, die repräsentative quantisierte Einträge darstellen. Ein hoher Prozentsatz ihrer gespeicherten Vektorelemente sind typischerweise Null-Einträge (> 2/3 der Elementeinträge) und die Codetabelle 210 ist daher eine dünnbesetzte Codetabelle.
Eine adaptive Codetabelle 215 enthält überlappende aktualisierte Vektoreinträge, die die bereits verarbeitete Sprache darstellen, und wird fortlaufend in jedem der Betriebsteilrahmen aktualisiert. Ihre Ausgabe wird durch ein über den Multiplizierer 216 angelegtes Verstärkungssignal verändert und dieses Signal mit Verstärkung wird in der Summierschaltung 217 mit der Ausgabe der stochastischen Codetabelle 210 summiert, die durch über den Multiplizierer 211 angelegte Verstärkung verändert wird.
Die Beschaffenheit der Sprachverarbeitung ist derart, daß die Sprache durch Betrachtung aufeinanderfolgender endlicher Intervalle des Sprachsignals codiert wird. Diese endlichen Intervalle sind als Rahmen 301, 302 und 303 bezeichnet. Die Verarbeitung findet wie durch das die Wellenform 306 in der Figur 3 umfassende Fenster dargestellt innerhalb eines Sprachfensters statt. Das Sprachsignal innerhalb jedes Rahmens wie beispielsweise dem Rahmen 301 ist in Teurahmen 311-314 aufgeteilt, um die Codierung des Sprachsignals zu erleichtern. Das Fenster schreitet fortlaufend fort und führt damit neue Einträge in die vorlaufenden Teilrahmen ein.
Der durch die Einrichtung der Figur 2 durchgeführte Gesamtcodierungsvorgang ist durch das Flußdiagramm der Figur 4 dargestellt. In den Vorgang wird am Endblock 401 eingetreten und er verläuft zum Block 403, um die LPC- (linear prediction coding)Analyse durchzuführen. Durch diesen Vorgang werden für das gegenwärtige interessierende Fenster lineare Prädiktionskoeffizienten abgeleitet. Hinsichtlich der Einrichtung der Figur 2 wird die codierte Sprache am Ausgang des linearen Prädiktionsfilters 220 auf Leitung 204 bereitgestellt, die einen die an Leitung 201 angelegte Eingangssprache darstellenden Bitstrom bereitstellt. Das lineare Prädiktionsfilter 220 liefert ein Digitalsignal, aus dem jede unnötige Redundanz aus dem codierten Sprachsignal entfernt worden ist, um die erforderliche Übertragungsbandbreite zu verringern.
Dieser Vorgang wird durch die Anweisungen der Blöcke 403 und 405 implementiert. Im Vorgang des Blockes 405 werden die im Block 403 bestimmten Koeffizienten quantisiert und codiert.
Der Teilrahmenindexzähler, der den aktiven Teilrahmen anzeigt, wird anfangs im Block 407 auf Null gesetzt, und der Flußvorgang schreitet über den Entscheidungsblock 409 fort, der auf die letzte Teilrahmenzählung gleich der Anzahl von Teilrahmen in einem Rahmen reagiert. Solange wie die Zählung unter der Anzahl von Teilrahmen im Rahmen liegt, läuft der Fluß zum Block 411 weiter, um die interpolierten Filterkoeffizienten zu berechnen, und zum Block 413, um die Spektralgewichtungsmatrix zu berechnen. Wenn die Teilrahmenzählung erreicht ist, schreitet der Vorgangsfluß zum Block 415 fort, dessen Anweisungen zur Berechnung des adaptiven Codetabellenzielvektors aus der ursprünglichen Spracheingabe wirken. Die Anweisungen des Blocks 415 spiegeln die zur Durchsuche der adaptiven Codetabelle 215 nach Figur 2 benutzte Ausgabe des Frequenzgewichtungsfilters 207 wider. Die adaptive Codetabelle wird im Block 417 unter Verwendung spektralgewichteter mittlerer quadratischer Verzerrungsmaße nach dem optimalen adaptiven Codetabellenvektor durchsucht.
Der Zielvektor der stochastischen Codetabelle wird nach den Anweisungen des Blocks 419 berechnet und die stochastische Codetabelle wird nach den Anweisungen des Blocks 421 durchsucht, um einen gespeicherten quantisierten Vektoreintrag zu finden, der dem Ist- Zielvektor des Eingangssprachsignals annähernd entspricht.
Die adaptive Codetabelle wird nach den Anweisungen des Blocks 423 aktualisiert und die Indizes von optimalen Codetabellenvektoren werden nach den 20. Anweisungen des Blocks 425 codiert. Wenn nicht alle Teilrahmen verarbeitet worden sind, schreitet der Vorgangsverlauf über Leitung 428 zum Eingang des Entscheidungsblocks 409 fort. Wenn alle Teilrahmen verarbeitet worden sind, läuft der Fluß zu Blöcken 429 und 431 weiter, die das Ende der CELP-Codierung für den Rahmen anzeigen.
Der Decodiervorgang zur Wiederherstellung des ursprünglichen Sprachsignals ist im Flußdiagramm der Figur 5 dargestellt. Dieser Vorgang ist im wesentlichen die Inverse des Vorgangs der Figur 4 und betrifft den Empfang von Sprache aus den empfangenen digitalen Parametern.
In den Vorgang wird am Ende 501 eingetreten und die empfangenen LPC-Parameter werden entpackt und nach Block 503 aus dem enpfangenen Bitstrom decodiert. Der Teilrahmenzähler wird nach den Anweisungen des Blocks 505 auf Null gesetzt und der Zähler wird im Entscheidungsblock 507 abgelesen. Solange wie die Zählung unter Drei liegt, schreitet der Fluß zum Block 509 fort, um interpolierte Filterkoeffizienten zu berechnen. Wenn die Zählung Drei gleicht, schreitet der Fluß direkt zum Block 511 fort, wo die optimalen Codetabellenvektoren aus dem ankommenden Bitstrom entpackt werden.
Im Block 513 wird die Ausführungsfolge für den Teilrahmen berechnet und nach den Anweisungen im Block 515 skaliert. Im Block 517 wird Sprache durch Durchführen der Erregungssignale durch das interpolierte Filter synthetisiert. Im Block 519 wird Fehlererkennung und -korrektur auf Grundlage der Signalenergie durchgeführt und die adaptive Codetabelle wird im Block 521 aktualisiert. Die Filterung zur Wiedergewinnung des übertragenen Sprachsignals wird im Block 523 durchgeführt. Im Entscheidungsblock 525 wird bestimmt, ob der letzte Teurahmen verarbeitet worden ist, und wenn er nicht verarbeitet worden ist, kehrt der Fluß zum Eingang des Entscheidungsblocks 507 zurück. Wenn der letzte Rahmen verarbeitet ist, werden durch den Vorgang die Rahmen im Block 527 aktualisiert und im Endblock 529 wird die CELP-Decodierung abgeschlossen.
Der als Block 421 in Figur 4 dargestellte Teilvorgang zur Durchsuche der stochastischen Codetabelle ist ein kritischer Teil des gesamten Codiervorgangs. Es ist daher von Bedeutung, daß er so schnell wie möglich durchgeführt werden kann. In vielen Fällen ist diese Codetabelle eine dünnbesetzte Codetabelle, das heißt eine, in der eine Mehrzahl ihrer Einträge Nullen sind. Der hier offenbarte Suchprozeß ist so ausgelegt, daß er eine überlappende Codetabelle aufnimmt, in der benachbarte Vektoren viele gemeinsame Einträge aufweisen, doch ist zu verstehen, daß der Überlappungszustand nicht für den beschriebenen Vorgang notwendig ist. Dieser Zustand wird nach der Erfindung ausgenutzt, um die Suche der Codetabelle zu beschleunigen. Der Gesamtvorgang der Durchführung dieser Suche ist in den Flußdiagrammen der Figuren 6 bis 12 dargestellt.
Bei diesem Vorgang der Flußdiagramme wird in Betracht gezogen, daß die stochastische Codetabelle eine dünnbesetzte Codetabelle der Größe CS mit den Einträgen {C(i)} ist. Die Codetabelle enthält die Vektoren mit Dimension N, wobei:
Der Wert NS stellt die Anzahl von Codetabellenvektoren dar und steht im Verhältnis zur Codetabellengröße CS durch folgenden Ausdruck:
CS=NS * N (2)
Die Codetabelle ist dünn besetzt und die meisten Elemente C(i) weisen daher den Wert Null auf. Bei Sprachverarbeitungssystemen wie hier beschrieben können die Null-Elemente bis zu 85% der Codetabelleneinträge umfassen. Bei der Durchsuche der Codetabelle ist ein kritischer Wert das L&sub2;-Standardentfernungsmaß zwischen einem Zielvektor t und jedem beliebigen Codetabellenvektor Ci. Dieses Maß wird durch folgenden Wert definiert:
i=(t-µiCi)TW(T-µiCi) (3)
Der Wert W ist eine symmetrische positive definite Fehlergewichtungsmatrix; der Wert µi ist die mit dem i-ten Vektor verbundene Verstärkung. Der optimale Wert der Verstärkung für den Vektor Ci wird durch folgenden Ausdruck definiert:
Die obige Gleichung ergibt die Istverstärkungswerte. Wenn die Verstärkungswerte in einer quantisierten Tabelle enthalten sind, wird der einer Istverstärkung am nächsten liegende Verstärkungswert benutzt. Der Optimalwert für die Verstärkung wird durch das Verhältnis des Korrelationsgliedes zum Energieglied der Matrix bestimmt. Korrelations- und Energieglieder sind in der Technik gut bekannt, und es wird nicht angenommen, daß sie ausführlich besprochen werden müssen. Der Wert µi ist gleich
Bei einem gegebenen Wert für Mi ist der optimale Index iopt derjenige Wert, der das Verzerrungsmaß i minimiert. Die Ausdrücke zum Ermitteln von i können entwickelt und das nichtkritische Glied, das nicht vom Index i abhängig ist, beseitigt werden. Der interessierende resultierende Ausdruck ist das Verzerrungsmaß i, wobei
i=µi²ei-2µi i
Das Korrelationsglied i kann berechnet werden durch Speichern der spektralen Gewichtungsmatrix, wobei
Y=(y(0),y(1),...y(N-1)]T = Wt (6)
und nachfolgendes Anwenden der Formel
Das Energieglied wird durch folgende Formel berechnet:
wobei W(l,k) der (l,k)-te Eintrag der Matrix W ist.
Es gibt zwei Informationsmengen, mit denen die dünne Besetzung der Codetabelle definiert wird und die zur Verbesserung des Wirkungsgrades der Berechnung dieser Korrelations- und Energieglieder benutzt werden. Die erste Information ist die Anzahl von Nicht-Null-Elementen (#NZE) in jedem Vektor Ci. Diese Elemente werden als Ni bezeichnet und als die Anzahl von Nicht-Null-Elementen im i-ten Codetabellenvektor definiert, d.h.
Ni=#NZE{C(iN),C(iN+1),...C(iN+N-1)}. (9)
Die zweite Information ist die Relativzeiger der Nicht-Null-Elemente. Diese Information wird nur dann für den i-ten Codetabellenvektor Ci bereitgestellt, wenn Ni # 0. Die aufeinanderfolgenden Relativzeiger der Nicht-Null- Elemente dieses Vektors beginnen alle von einem geeigneten Bezugspunkt aus. Wenn daher C(iN+l&sub1;),C(iN+l&sub2;),...C(iN+lNi) die Nicht-Null-Elemente von Ci darstellt, dann sind die aufeinanderfolgenden Relativzeiger beginnend von C(iN) durch folgende Glieder gegeben:
Diese Information wird für jeden Vektor gespeichert. Mit den obigen Informationen bezüglich der dünnen Besetzung der Codetabelle können die notwendigen Energie- und Korrelationsglieder nunmehr mit großer Verringerung des Rechenaufwandes leicht berechnet werden.
Bei dem Korrelationsglied:
Bei dem Energieglied:
und wobei lk und lj der Definition durch Gleichung (12) entsprechen.
Das obige Verfahren erzeugt eine bedeutende Verringerung bei der Operation Multiplizieren/Zählung Addieren auf Registerebene von O(N) zu O(Ni) im Fall des Korrelationsgliedes und von O(N²) zu O(N ) im Fall des Energiegliedes. Wenn mehr als zwei Drittel der Codetabelleneinträge Null sind, wird eine bedeutende Verringerung des Rechenaufwandes erreicht.
Weitere Verbesserungen in der Berechnung können erhalten werden, wenn die Codetabelleneinträge zusätzlich einander überlappen und wenn die Fehlergewichtungsmatrix W eine Toeplitz-Matrix ist. Eine überlappende Codetabelle ist eine, bei der benachbarte Vektoren gemeinsame Ele mente teilen. Es ist wahrscheinlich, daß diese Merkmale bei Codetabellen für niedrigratige CELP-Codierer vorkommen. Die Hilfsinformationen können weiterhin durch Ausnutzung der Überlappungseigenschaft der Codetabelle und der Toeplitz-Fehlergewichtungsmatrix W verändert werden, um wirksame Berechnung zu erleichtern.
Im Fall einer überlappenden dünnbesetzten Codetabelle von Größe CS mit den Einträgen {C(i)}, wobei 0≤i≤CS-1 und wobei N die Vektordimension und d der Überlappungsgrad ist, sind die Codetabellenvektoren durch folgenden Ausdruck gegeben:
Hierbei ist NS die Anzahl von Codetabellenvektoren und steht mit der Codetabellengröße durch das folgende Verhältnis in Beziehung:
CS=(N&sub5;-1)*d+N (16)
Wie in dem oben beschriebenen allgemeinen Fall ist das optimale Indexglied dasjenige Glied, das das Verzerrungsmaß i minimiert, das eine Kombination der Energie- und Korrelationsglieder ist. Der Ausdruck ist:
i=µi²ei-2µi i (17)
ei ist das Energieglied CiTWCi und i ist das
W=[W(i,j)]NXN=[W(i-j,0]NXN (18)
Die Matrix W ist eine Toeplitz-Matrix. Für diesen Sonderfall wird das Korrelationsglied durch Speichern der Werte Y=Wt und Verwendung der Gleichung:
zur Berechnung für das Korrelationsglied berechnet.
Das Energieglied wird unter Ausnutzung der dünnen Besetzung der Codetabelle und des Toeplitz-Prinzips der Matrix W berechnet. Die folgenden rekursiven Beziehungen werden für den ersten Codetabellenvektor für i = 0 abgeleitet:
Dieser Ausdruck wird vorberechnet und gespeichert. Bei 1≤i≤NS-1 gibt es folgende Ausdrücke:
Die Hilfsinformationen werden durch diese Teilsummen und das Korrelationsglied verändert. Im Fall der ersten Teilsumme Δk,1 ist die Anzahl Nk,1 nichttrivialer Multiplizier-Addier-Operationen durch folgenden Ausdruck gegeben:
Nk,1=0; wenn C(k+N)=0 und
Nk,1=#NZE{C(k+N-1),...C(k+1)}; wenn C(k+N) # 0 (27)
Im Fall der zweiten Teilsumme Δk,2 ist die Anzahl nichttrivialer Multiplizier-Addier-Operationen Nk,2 durch folgenden Ausdruck gegeben:
Nk,2=0; wenn C(k)=0 und
Nk,2=#NZE{C(k+1),...C(k+N-1)}; wenn C(k) # 0 (28)
Für den Fall des Korrelationsgliedes i ist die Anzahl nichttrivialer Multiplizier-Addier-Operationen Ni durch folgenden Ausdruck gegeben:
Ni=#NZE{C(id),C(id+1),...C(id+N-1)} (29)
Die zweite Menge von Hilfsinformationen besteht aus aufeinanderfolgenden Relativzeigern jedes Nicht-Null- Elements der bei diesen Summen benutzten Codetabelle beginnend von einem geeigneten Bezugspunkt. Wenn daher
Nk,1 # 0 und die Elemente
C(k+N-l&sub1;), C(k+N-l&sub2;),...C(k+N-lNk,1) (30)
nichtnull sind, dann sind die aufeinanderfolgenden Relativzeiger vom Bezugspunkt C(k+N) aus durch folgende Ausdrücke gegeben:
Ähnlicherweise sind, wenn Nk,2 # 0 und die Elemente C(k+r&sub1;), C(k+r&sub2;),...C(k+rNk,2) nichtnull sind, die aufeinanderfolgenden Relativzeiger von C(k) aus durch folgende Ausdrücke gegeben:
Schließlich sind, wenn Ni # 0 und die Elemente C(id+S&sub1;), C(id+S&sub2;),...C(id+SNi) nichtnull sind, die aufeinanderfolgenden Relativzeiger von C(id) aus gegeben durch
Die vorgespeicherten Ejifsinformationen werden zur Berechnung von Δk,1 unter Verwendung folgender Gleichungen benutzt:
Wobei:
Der Wert für Δk,2 kann wie folgt berechnet werden:
wobei:
Der Wert von i wird durch folgenden Ausdruck berechnet
wobei:
Die entwickelten Hilfsinformationen bewirken die bedeutsame Verringerung der an der Codetabellensuche beteiligten Berechnungen. In diesem Verfahren wird die dünne Besetzung der Codetabelle zum höchsten Grad ausgenutzt, zusätzlich zur Ausnutzung der Überlappung in der Codetabelle und des Toeplitz-Matrix-Prinzips der Fehlergewichtungsmatrix W.
Das Verfahren zur Entwicklung und Ausnutzung der Hufsinformationen ist in den Flußvorgängen der Figuren 6-12 offenbart. Die Vorgänge der Figuren 6, 7 und 8 bewirken die Erzeugung der Hufsinformationen. Der Vorgang der Figuren 9 und 10 benutzt die Hilfsinformationen beim Erreichen der Codetabelle. Der Vorgang der Figuren 11 und 12 sind im Vorgang der Figuren 9 und 10 benutzte Teilvorgänge.
Der Vorgang der Figur 6 bewirkt die Erzeugung von Hilfsinformationen, die die Überlappung in der dünnbesetzten Codetabelle definieren. Der Vorgang beginnt beim Eingangsanschluß 601 in der Figur 6. Die Codetabelle ist als eine Größe CS aufweisend definiert und ihre Einzeleinträge C(i) werden in den Vorgang eingetragen. Die Codetabelle enthält NS Vektoren mit der Dimension N. Die Einträge der Vektoren sind als eine Überlappung zum Grad d aufweisend angegeben.
Bei im Vorgang eingegebener Codetabelle wird ein Zähler auf den Wert i=-1 im Block 605 initialisiert. Dieser Zählerwert wird nach dem Ausdruck i=i+1 im nächsten Block 607 um 1 erhöht. Die Anzahl von Nicht- Null-Elementen Ni im i-ten Codetabellenvektor wird im Speicher gespeichert, der dem Vorgang nach Block 609 dient. Ihr Wert wird durch Gleichung (29) gegeben. Die Einträge des i-ten Codetabellenvektors nehmen die folgende symbolische Form an:
{C(id),C(id+1),...C(id+N-1)}
Der Vorgang des Entscheidungsblocks 611 bestimmt, ob der Wert von Ni Null ist. Wenn die Antwort nein ist, werden die Relativzeigerstellungen der Nicht-Null- Elemente in der Form der Gleichung (33) bestimmt und aufgezeichnet und nach den Anweisungen des Blocks 613 gespeichert. Der Vorgang des Entscheidungsblocks 615 bestimmt, ob der Index i gleich NS-1 ist. Wenn die Antwort nein ist, dann schreitet der Vorgang zum Block 607 fort. Ansonsten schreitet der Vorgang zum Block 617 fort und gibt die Teilsummen betreffenden Hilfsinformationen zur Beschleunigung der Korrelationsberechnungen aus.
Der Vorgang der Figur 7 zur Bestimmung der Hufsinformationen zur Beschleunigung der Berechnung des Energiegliedes und des Korrelationsgliedes wird im Beginnanschluß 701 begonnen. Die dünnbesetzte Codetabelle der Größe CS wird durch die Anweisungen des Blocks 703 in den Vorgang eingeführt. Der Zähler des Blocks 705 wird auf den Wert -1 initialisiert und sofort im Block 707 erhöht. Im Entscheidungsblock 709 wird bestimmt, ob der Wert C(k+N)=0 ist. Wenn der Wert ja ist, dann wird das Element Nk,1 gleich Null gesetzt. Wenn der Wert nein ist, dann wird das Element Nk,1 gleich der Anzahl von Nicht- Null-Elementen in der Folge mit Länge {C(k+1),...C(k+ N-1)} im Block 713 gesetzt. Diese Werte werden nach Gleichung (27) bestimmt.
Der Flußvorgang schreitet zum Entscheidungsblock 715 fort, um zu bestimmen, ob das Element Nk,1 gleich Null ist. Wenn ja, dann schreitet der Fluß zum Entscheidungsblock 719 fort. Wenn nein, dann schreitet der Fluß zum Funktionsblock 717 fort, um die Relativzeigerstellungen nach Gleichung (31) der Nicht- Null-Elemente zu speichern.
Im nächsten Entscheidungsblock 719 wird bestimmt, ob der Wert C(k) gleich Null ist. Wenn ja, dann wird der Wert Nk,2 im Block 723 auf Null gesetzt. Wenn nein, dann wird der Wert von Nk,2 auf die Anzahl von Nicht-Null- Elementen nach Gleichung (28) im Block 721 gesetzt. Der Fluß des Vorganges schreitet zum Entscheidungsblock 725 fort, um zu bestimmen, ob der Wert von Nk,2 gleich Null ist. Wenn nein, dann schreitet der Fluß zum Block 727 fort, bei dem die Relativzeigerstellungen der Nicht-Null-Elemente nach Gleichung (32) gespeichert werden. Der Fluß schreitet zum Entscheidungsblock 729 fort, um den Ausdruck k=(NS-1)d-1 auszuwerten. Wenn der Ausdruck nicht gültig ist, kehrt der Fluß zum Eingang zum Block 707 zurück und der Vorgang wiederholt sich. Wenn der Ausdruck gültig ist, dann schreitet der Fluß zum Block 731 fort, um die entwickelten Hilfsinformationen zur Verwendung bei der Durchsuchung der dünnbesetzten Codetabelle zu speichern.
Der Vorgang der Figuren 9 und 10 (die wie in Figur 14 gezeigt verbunden sind) bewirkt die Verwendung der erzeugten Hilfsinformationen bei der Durchsuchung der Codetabelle. In den Flußvorgang wird beim Beginnanschluß 801 eingetreten und zum Funktionsblock 803 fortgeschritten, bei dem die überlappende dünnbesetzte Codetabelle mit Größe C&sub2; eingegeben wird, die NS Vektoren der Dimension N enthält. Der Fluß schreitet zum Block 805 fort, um die Autokorrelation des ersten Codetabellenvektors, die das erste Energieglied initialisiert, einzugeben. Diese Werte werden durch Gleichung (21) gegeben. Die Verzerrungsmetrik für einen allgemeinen Codetabellenvektor wird nach Gleichung (17) im Block 807 bestimmt und in den Vorgang eingegeben und der gewichtete Zielvektor Y von Dimension N wird im Block 809 eingegeben.
Der Vorgangszähler für i wird im Block 811 auf Eins initialisiert. Das Energieglied ei wird im Block 813 nach Gleichung (20) unter Verwendung des vorher bestimmten vorgespeicherten Autokorrelationsgliedes des ersten Codetabellenvektors berechnet. Das Korrelationsglied i wird durch Gleichung (19) im Block 815 berechnet. Der Wert der Verstärkung µi, die die Verzerrungsmetrik i minimiert, wird aus einer vorbestimmten Tabelle quantisierter Verstärkungswerte im Block 817 ausgewählt. Die Mindestverzerrungsmetrik opt wird auf den Wert i initialisiert und der optimale Indexwert iopt wird im Block 819 auf i initialisiert.
Der Vorgangszähler wird im Block 821 um Eins erhöht. Das Energieglied wird unter Verwendung der Gleichung (22) im Block 823 und durch Verwendung des im Flußdiagramm der Figur 11 ausführlich dargestellten Vorgangs berechnet. Das Korrelationsglied wird unter Verwendung der Gleichung (19) im Block 823 und durch Verwendung des ausführlich im Flußdiagramm der Figur 12 dargestellten Vorgangs berechnet.
Ein Verstärkungswert µi, der die Verzerrungsmetrik i minimiert, wird nach den Anweisungen des Blocks 827 aus der Quantisierungstabelle ausgewählt. Im Entscheidungsblock 829 wird bestimmt, ob die berechnete Verzerrungsmetrik i der Mindestwert ist. Wenn ja, dann werden die Werte von UOPT und ihre Indexnummer iopt im Block 831 auf i und i gesetzt und der Vorgangsfluß schreitet zum Entscheidungs block 833 fort. Wenn die Verzerrungsmetrik i nicht minimal ist, schreitet der Fluß direkt zum Entscheidungsblock 833 fort.
Im Entscheidungsblock 833 wird bestimmt, ob der Wert für die Indexnummer i gleich dem Glied NS-1 ist. Wenn die Gleichheit gilt, schreitet der Vorgang zum Block 835 fort, um das optimale Indexglied iopt auszugeben, und der Vorgang hält beim Anschlußblock 837 an. Wenn der Wert für i nicht gleich NS-1 ist, kehrt der Fluß zum Eingang zum Block 821 zurück, wo der Zähler erhöht wird und der Vorgang weiterläuft.
Der Vorgang zum Berechnen des Energiegliedes ei ist in der Figur 11 offenbart und beginnt am Beginnanschluß 901. Der erste Schritt besteht in der Eingabe des aktuellen Vektorindexes im Block 903. Im Block 905 wird das vorherige Energieglied ei-1 eingegeben und die Codetabelleneinträge C(k) werden im Block 907 für die Werte (i-1)d≤k≤id-1+N eingegeben. Die in den Flußvorgängen der Figuren 6, 7 und 8 entwickelten Hilfsinformationen einschließlich Nk,1 Nk,2 und zugehörigen Relativzeiger werden im Block 909 eingegeben. Die gewichteten Matrixeinträge werden im Block 915 eingegeben.
Der Zähler für den Wert k wird im Block 915 auf den Wert k=(i-1)d-1 initialisiert und das Energieglied ei wird im Block 917 auf den Wert ei-1 initialisiert. Der Zähler für k wird im Block 919 erhöht und im Block 920 wird unter Verwendung der Gleichungen (34), (35) und (36) die erste Teilsumme Δk,1 berechnet. Im Block 921 wird unter Verwendung der Gleichungen (37), (38) und (39) die zweite Teilsumme Δk,2 berechnet, im Block 923 wird unter Verwendung der Gleichung (25) die dritte Teilsumme Δk,3 berechnet und im Block 925 wird unter Verwendung der Gleichung (26) die vierte Teilsumme Δk,4 berechnet. Im Block 927 wird der Wert für ei aktualisiert und im Entscheidungsblock 929 wird der Wert von k ausgewertet. Wenn der Wert von k id-1 ist, dann wird der Wert von im Block 931 ausgegeben. Wenn der Wert für k nicht id-1 ist, kehrt der Fluß zum Eingang zum Block 917 zurück und der Vorgang wiederholt sich.
Im Flußdiagramm der Figur 12 ist der Vorgang zur Bestimmung des Korrelationsgliedes i offenbart. Beginnend am Beginnanschluß 1001 ist der erste Schritt die Eingabe der Codetabelleneinträge, Eingabe des aktuellen Vektorindexes i und von C(k) im Block 1005 für id≤k≤id+N-1. Die in den Flußdiagrammen der Figuren 6, 7 und 8 entwickelten Hilfsinformationen Ni und Relativzeiger werden im Block 1007 eingegeben. Die Gewichtungsmatrixeinträge werden im Block 1009 eingegeben und der gewichtete Zielvektor wird im Block 1011 eingegeben.
Im Entscheidungsblock 1013 wird bestimmt, ob der Wert von Ni gleich Null ist. Wenn er der Wert von i ist, wird er im Block 1017 auf Null gesetzt. Wenn er nicht der Wert von i ist, wird er unter Verwendung von Gleichungen (40), (41) und (42) im Block 1015 berechnet. Der Wert von i wird im Block 1019 ausgegeben.

Claims

1. Sprachverarbeitungsschaltung für ein Funkübertragungssystem mit folgenden:

einem Eingang (100) zur Aufnahme von Analogsprache;

einem Analog-Digital-Signalwandler (101) zum Umwandeln der Analogsprache in Digitalsignale; Sprachcodierschaltung (102) zum Codieren der digitalen Sprachsignale; mit Schaltungen zur Codierung des digitalen Sprachsignals als eine Zielvektorgröße;

einer dünn besetzten Codetabelle (210) mit einer darin gespeicherten Mehrzahl von Codetabellevektoren; Mitteln zum Zuordnen einer Indexnummer zu jedem zufallsmäßigen Codetabellenvektor;

Suchmitteln zum Auswählen eines Vektors aus der dünn besetzten Codetabelle, der sich am nächsten an die Zielvektorgröße des digitalen Sprachsignals annähert; wobei die besagten Suchmittel folgendes enthalten:

Mittel (829-835) zum Bestimmen eines Entfernungs wertes zwischen dem Zielvektor und den zufallsmäßigen Vektoren der Codetabelle; und

Mittel (829-835) zum Bestimmen der optimalen mit einem Entfernungswert verbundenen Indexnummer zum Mmimieren des Entfernungswertes zwischen dem Codetabellenvektor und dem Zielvektor; und

Mittel zum Übertragen der Indexnummer über Funkübertragungs signale;

dadurch gekennzeichnet, daß die besagten Suchmittel folgendes enthalten:

Mittel (603-609) zum Bestimmen und Speichern der Anzahl von Nicht-Null-Elementen in jedem Codetabellenvektor;

Mittel (613-615) zum Bestimmen und Speichern der aufeinanderfolgenden Relativzeiger der Nicht-Null- Elemente für jeden Codetabellenvektor als Anfangsbezugspunkt;

Mittel (803-813) zum Berechnen eines Korrelationsgliedes zwischen den Codetabellenvektoren und dem Zielvektor durch Summieren der Produkte der Nicht-Null- Elemente der Codetabellenvektoren und der entsprechenden Elemente der Zielvektoren unter Benutzung von gespeicherten aufeinanderfolgenden Relativzeigern;

Mittel (821-823) zum Berechnen eines Energiegliedes für die Codetabellenvektoren durch Summieren von nur bestimmten Nicht-Null-Elementen;

Mittel (825) zum Bestimmen von mit jedem zufallsmäßigen Codetabellenvektor verbundenen Verstärkungswerten als Verhältnis zwischen dem Korrelationsglied und dem Energieglied;

und daß der besagte Entfernungswert als eine Differenz zwischen den verstärkungsmodifizierten Korrelationsgliedern und verstärkungsmodifizierten Energiegliedern der Codetabellenvektoren bestimmt wird.

2. Sprachverarbeitungsschaltung für ein Funkübertragungssystem nach Anspruch 1, weiterhin mit folgenden:

Mitteln zum Bestimmen eines Überlappungsgrades von Vektoren in der Codetabelle; und

Mitteln zum Nutzen des Überlappungsgrades zur Berechnung der Energie- und Korrelationsglieder.

3. Sprachverarbeitungsschaltung für ein Funkübertragungssystem nach Anspruch 2, weiterhin mit folgenden: Mitteln zum Bestimmen einer Verzerrungsmetrik und Mitteln zur Benutzung der Verzerrungsmetrik zur Auswahl eines Verstärkungswertes.

4. Verfahren zur Verarbeitung von Sprache in einem Funktelekommunikationssystem, mit folgenden Schritten: Codieren eines digitalen Sprachsignals durch folgende Schritte:

Umwandeln des digitalen Sprachsignals in eine Zielvektorgröße;

Speichern einer Mehrzahl von zufallsmäßigen Codetabellenvektoren in einer gespeicherten Codetabelle mit einem dünn besetzten Inhalt von Instanzen, so daß mindestens eine Mehrheit der Elementinstanzen einen Wert Null aufweisen;

Zuordnen einer Indexnummer zu jedem zufallsmäßigen Codetabellenvektor;

Durchsuchen der Codetabelle zur Auswahl eines zufallsmäßigen Codetabellenvektors, der dem Zielvektor am besten entspricht;

wobei der Schritt des Suchens folgendes umfaßt:

Bestimmen eines Entfernungswertes zwischen dem Zielvektor und den zufallsmäßigen Vektoren der Codetabelle; und

Bestimmen der optimalen, mit einem Entfernungswert verbundenen Indexnummer zum Minimieren des Entfernungswertes zwischen dem Codetabellenvektor und dem Zielvektor; und

Übertragen der Indexnummer mit Funksignalen; dadurch gekennzeichnet, daß das besagte Durchsuchen folgende Schritte umfaßt:

Bestimmen und Speichern der Anzahl von Nicht- Null-Elementen in jedem Codetabellenvektor; Bestimmen und Speichern der aufeinanderfolgenden Relativzeiger der Nicht-Null-Elemente für jeden Codetabellenvektor als Anfangsbezugspunkt;

Berechnen eines Korrelationsgliedes zwischen den Codetabellenvektoren und dem Zielvektor durch Summieren der Produkte der Nicht-Null-Elemente der Codetabellenvektoren und der entsprechenden Elemente der Zielvektoren unter Benutzung gespeicherter aufeinanderfolgender Relativzeiger;

Berechnen eines Energiegliedes für die Codetabellenvektoren durch Summieren von nur bestimmten Nicht-Null-Elementen;

Bestimmen von mit jedem zufallsmäßigen Codetabellenvektor verbundenen Verstärkungswerten als Verhältnis zwischen dem Korrelationsglied und dem Energieglied;

und daß der besagte Entfernungswert als Differenz zwischen den verstärkungsmodifizierten Korrelations -gliedern und verstärkungsmodifizierten Energiegliedern der Codetabellenvektoren bestimmt wird.

5. Verfahren zur Verarbeitung von Sprache in einem Funktelekommunikationssystem nach Anspruch 4, weiterhin mit folgenden Schritten:

Bestimmen eines Überlappungsgrades von Codetabellenvektoren;

Ableiten und Speichern von rekursiven Verhältnissen aus der Überlappung von Codetabellenvektorinstanzen und

Bestimmen der Energieglieder durch weitere Nutzung von Teilsummen der rekursiven Verhältnisse.

6. Verfahren zur Verarbeitung von Sprache in einem Funktelekommunikationssystem nach Anspruch 5, wobei die Korrelationsglieder durch weitere Nutzung von Teilsummen der rekursiven Verhältnisse bestimmt werden.

7. Verfahren zur Verarbeitung von Sprache in einem Funktelekommunikationssystem nach Anspruch 6, wobei der Schritt des Bestimmens des Verstärkungswertes folgendes umfaßt:

Vergleichen eines als Verhältnis zwischen dem Korrelationsglied und dem Energieglied bestimmten Verstärkungswertes mit einer gespeicherten Mehrzahl von Verstärkungswerten und Auswählen des dem Wert des Verhältnisses nächstgelegenen gespeicherten Verstärkungs wertes.