DE60319501T2

DE60319501T2 - Verfahren und Gerät zur Punktierung von Kodesymbolen

Info

Publication number: DE60319501T2
Application number: DE2003619501
Authority: DE
Inventors: Aki 94087 Sunnyvale Shohara
Original assignee: Broadcom Corp
Current assignee: Broadcom Corp
Priority date: 2003-02-05
Filing date: 2003-02-05
Publication date: 2009-04-02
Anticipated expiration: 2023-02-06
Also published as: DE60319501D1; EP1445885A1; EP1445885B1

Description

Die vorliegende Erfindung betrifft Verfahren und eine Vorrichtung zum Komprimieren und Entkomprimieren von Punktiermasken zur Verwendung in drahtlosen Kommunikationssystemen.
HINTERGRUND DER ERFINDUNG
Eine Zielsetzung in Kommunikationssystemen ist es, Signale unter Verwendung einer minimalen Übertragungskanalbandbreite zu übertragen und zu empfangen und die Gesamtfehlerrate unter einem annehmbaren Schwellwert zu halten. Die Kanalbandbreite wird von Sendern gefüllt, die ständig mehr Daten zu senden versuchen. Fehler treten aufgrund von Interferenz und Kanalbeschränkungen auf, welche die Daten verfälschen. Systeme, die Daten senden und empfangen, umfassen Mobiltelefone, Personal Digital Assistants (PDAs), Lokalbereichsnetze (LANs), Weitbereichsnetze (WANs) und dergleichen. Solche Systeme können von Einheit zu Einheit kommunizieren, wie etwa von Mobiltelefon zu Mobiltelefon, oder können Basisstationen, Schüsselantennen, Satelliten und dergleichen verwenden.
Sendesignale werden auf vielfache Weise korrumpiert, bevor sie den vorgesehenen Empfänger erreichen. Interferenz von Signalen, die von anderen Sendequellen gesendet werden, Lecks aus Stromleitungen und fest verdrahteten Kommunikationssystemen und dergleichen bewirken allesamt eine Korruption eines gewünschten Signals. Im Allgemeinen sendet ein drahtloser Sender das Sendesignal in alle Richtungen aus. Dieses Sendesignal wird von Gebäuden, Bäumen und dergleichen zurückgeworfen oder reflektiert. Der Abschnitt eines Signals, das entlang eines direkt zum Empfänger führenden Pfades gesendet wird, erreicht den Empfänger. Jedoch erreichen auch Abschnitte des Signals, die von einem Gebäude auf den Empfänger hin reflektiert werden, den Empfänger. Dieser letztere Abschnitt des Signals erreicht den Empfänger zu einem späteren Zeitpunkt als der erste Abschnitt des Signals, was eine Art der Interferenz verursacht, die als Mehrwegeausbreitung bzw. Mehrwegeempfang bekannt ist. Diese und auch andere Störungsquellen machen es für einen Empfänger sehr schwer, ein Sendesignal mit einem annehmbaren Genauigkeitsgrad zu empfangen, und erhöhen die Häufigkeit von Fehlern. Die Rate, mit der Fehler in Kommunikationssystemen auftreten, wird als die Anzahl von übertragenen Informationsbits ausgedrückt und als die Bitfehlerrate oder BER (Bit Error Rate) bezeichnet.
Ein herkömmliches Verfahren zur Verringerung der BER eines Kommunikationssystems ist es, jedem ursprünglichen Symbol, das an einen Empfänger gesendet werden soll, eine Serie von als Chips bezeichneten Symbolen zuzuordnen, die tatsächlich gesendet werden. Dieser Zuordnungsvorgang wird als Codierung bezeichnet. Die Anzahl von zu sendenden Symbolen, geteilt durch die Anzahl von tatsächlich gesendeten Chips, ist als die Codierrate bekannt. Mit anderen Worten ist die Codierrate das Verhältnis der Codierereingaberate zur Codiererausgaberate. Die in dieser Codierung inhärente Redundanz ermöglicht eine ordnungsgemäße Decodierung der empfangenen Daten durch den Empfänger auch dann, wenn Fehler beim Empfang von individuellen Chips vorliegen. Die codierten Anwenderdaten werden als das Codewort bezeichnet.
Als ein einfaches Beispiel sei angenommen, dass in einem binären System das Symbol 1 an einen Empfänger gesendet werden soll. Wenn das Symbol 1 gesendet und durch eine Interferenz korrumpiert wird, so dass es für den Empfänger wie eine 0 aussieht, ist ein Fehler aufgetreten. Stattdessen kann ein System verwendet werden, in dem die Serie von Chips 101 anstelle der 1 gesendet werden kann, und 010 für jede 0 gesendet werden kann. D. h., eine 1 wird als 101 codiert, und eine 0 wird als 010 codiert. Die Codierrate für dieses System ist 1/3, da 3 Chips für jedes Bit gesendet werden. Wenn 101 gesendet wird und eine Interferenz das 1. Chip so korrumpiert, dass er für den Empfänger wie eine 0 aussieht, empfängt der Empfänger die Serie 001. Da 001 von 101 nur durch 1 Chip verschieden ist, aber von 010 durch 2 Chips verschieden ist, kann der Empfänger einfach annehmen, dass 101 gesendet wurde, was einer 1 entspricht. In dieser Situation hat sich kein Bitfehler ereignet, obgleich es einen Chipfehler gegeben hat.
Der Nachteil eines solchen Systems ist es, dass die Rate von Informationen, die sich vom Sender zum Empfänger bewegen, auf 1/3 verringert ist, da jedes an den Empfänger gesendete Bit die Übertragung von drei Chips erfordert. In Situationen, in denen die Interferenz relativ gering ist, wird diese 3:1-Redundanz zu einer unnötigen Verschwendung von Übertragungsbandbreite. Es ist wünschenswert, einen optimalen Kompromiss zu erzielen, bei dem die Coderate gerade noch ausreichend ist, um die durch den verwendeten Standard spezifizierten BER-Kriterien zu erfüllen. Bei dem oben stehenden Beispiel kann es beispielsweise wünschenswert sein, nur zwei Chips pro Bit an den Empfänger zu senden. Ein für seine Effektivität bei der Einstellung der Coderate bekanntes Verfahren ist die Verwendung einer Punktiermaske, wobei ausgewählte Bits des Codewortes gemäß der Definition durch die Punktiermaske nicht übertragen werden. Eine Punktiermaske ist eine binäre Sequenz, welche die gleiche Länge wie das Codewort besitzt, wobei eine Null in der Punktiermaske angibt, dass das Bit nicht gesendet wird, und eine Eins angibt, dass es gesendet wird. Auf der Empfangsseite gibt eine Null eine Position an, an der eine Löschung einzusetzen ist. Eine Löschung ist eine Angabe für den Decoder, dass eine Zweideutigkeit bezüglich des Wertes des empfangenen Bits vorliegt.
Wenn eine Anwenderdatenserie codiert wurde, kann die Punktiermaske verwendet werden, um Chips zu löschen und dadurch die verfügbare Bandbreite besser zu nutzen. Wenn beispielsweise jedes zu übertragende Symbol als 3 Chips codiert wird, betrüge die Coderate 1/3. Wenn dann jedes dritte Chip entfernt wird, beträgt die resultierende Coderate 1/2. Wenn man über eine Vielfalt von verwendbaren Punktiermasken verfügt, können ein Empfänger und ein Sender die Codierung so einstellen, dass die verschwendete Bandbreite minimiert und gleichzeitig die BER unter einem annehmbaren Schwellwert gehalten wird.
1 zeigt eine herkömmliche Verwendung einer Punktiermaske. Die Serie Ti 110 ist die Anwenderdaten, die ein Sender einem Empfänger senden möchte. Die Serie Ti 110 wird zuerst in die längere Serie Wi 120 codiert, die das Codewort darstellt. Dann wird eine Punktiermaske Pi 130 verwendet, welche in Bits die gleiche Länge wie das Codewort Wi 120 besitzt. Für jede 1 in der Punktiermaske wird der entsprechende Chip übertragen. Für jede 0 in der Punktiermaske findet eine Löschung oder Streichung statt, und das entsprechende Chip wird nicht übertragen. Diese Löschungen resultieren in einer kürzeren Datenserie Ei 140, die an den Empfänger gesendet wird.
Ei 140 wird vom Sender gesendet und durch eine Interferenz verfälscht, bevor es empfangen wird. Was tatsächlich empfangen wird, ist in 2 als Empfangsdaten Ri 210 gezeigt. Sobald Ri 210 vom Empfänger empfangen wird, muss die vorstehende Operation umgekehrt durchgeführt werden. Daher muss dem Empfänger die gleiche Punktiermaske Pi 220 zur Verfügung stehen wie diejenige, die von dem Sender in 1 verwendet wurde. 2 zeigt eine Empfangsdatenserie Ri 210 und die Punktiermaske Pi 220. Für jede 1 in der Punktiermaske Pi 220 ist das entsprechende Empfangsdatenchip als codierte Empfangsdaten zu sehen. Für jede 0 in der Punktiermaske Pi 220 wird eine Löschung nach dem vorherigen Chip in die empfangenen Anwenderdaten eingefügt. Dies resultiert in der codierten Empfangsdatenserie Si 230. Diese codierte Empfangsdatenserie Si 230 kann dann in die empfangenen Anwenderdaten Ui 240 decodiert werden, die – falls alles ordnungsgemäß abläuft – mit der Anwenderdatenserie Ti 110 in 1 identisch sind.
Wie aus dem Vorstehenden ersichtlich ist, müssen sowohl die Sendeeinheit als auch die Empfangseinheit Zugriff auf die Punktiermaske Pi 220 haben. Die Länge jeder Punktiermaske Pi 220 ist genauso lang wie das Codewort Wi 120 in 1, welches die gleiche Länge wie die codierte Empfangsdatenserie Si 230 in 2 hat.
Einige Standards der drahtlosen Kommunikation umfassen eine Vielfalt von verwendbaren Punktiermasken. Die Verwendung dieser Punktiermasken ermöglicht eine Optimierung der Codierrate über einen breiten Bereich von Übertragungskanalbedingungen. Bei herkömmlichen Punktiereinrichtungen wird die Punktiermaske einfach in einem Speicher abgelegt. Eine einfache Speicherung der Punktiermasken macht jedoch einen ziemlich großen Speicher auf einem VLSI-Chip erforderlich, der dazu entworfen ist, diese Drahtlos-Standards zu implementieren.
Die EP 0 966 124 A2 beschreibt ein Verfahren und ein System zum Senden und Empfangen von punktierten, faltungscodierten Daten, bei denen eine Referenzmatrix zum Erzeugen mehrerer Formen von Punktiermustern vorgesehen ist. Diese Punktiermuster werden beispielsweise durch Konvertieren der Referenzmatrix erstellt. Es wird daher nur eine Matrix als Referenz gespeichert, um Speicherraum zu sparen.
Es ist jedoch wünschenswert, mehrere verschiedene Punktiermasken auf effiziente Weise in einer integrierten Schaltung speichern zu können.
Diese Aufgabe wird durch das Verfahren und die Vorrichtung für die Komprimierung von Punktiermaskeninformationen gemäß den Ansprüchen 1 bzw. 19 sowie durch das Verfahren und die Vorrichtung für die Entkomprimierung und Verwendung einer Punktiermaske gemäß den Ansprüchen 8 bzw. 26 gelöst.
Vorteilhafte Ausführungsformen der Erfindung sind in den abhängigen Unteransprüchen angegeben.
Die nachfolgende detaillierte Beschreibung und die beigefügte Zeichnung ermöglichen ein besseres Verständnis der Beschaffenheit und der Vorteile der vorliegenden Erfindung.
KURZBESCHREIBUNG DER ZEICHNUNG
1 zeigt ein herkömmliches Codieren und Punktieren von Anwenderdaten vor ihrer Übertragung;
2 zeigt ein herkömmliches Füllen mit Löschungen und Decodieren einer Empfangsdatenserie;
3 zeigt ein Verfahren zum Komprimieren und Entkomprimieren einer Punktiermaske;
4 zeigt ein Verfahren zum Komprimieren einer allgemeinen Punktiermaske unter Verwendung einer differentiellen Punktiermaske gemäß der vorliegenden Erfindung;
5 zeigt ein Verfahren zum Komprimieren einer konkreten Punktiermaske unter Verwendung einer differentiellen Punktiermaske gemäß der vorliegenden Erfindung;
6 zeigt ein Verfahren zum Rekonstruieren einer Punktiermaske aus einer gespeicherten, komprimierten differentiellen Punktiermaske für den allgemeinen Fall;
7 zeigt ein Verfahren zum Rekonstruieren einer Punktiermaske aus einer gespeicherten, komprimierten differentiellen Punktiermaske für einen konkreten Fall;
8 ist ein Ablaufdiagramm zum Komprimieren von Punktiermasken für die elektronische Speicherung gemäß der vorliegenden Erfindung;
9 ist ein Ablaufdiagramm entweder zum direkten Lesen von Punktiermasken oder zum Entkomprimieren von Punktiermasken aus einer elektronischen Speicherung gemäß der vorliegenden Erfindung;
10 ist ein Blockdiagramm einer Vorrichtung, die zum Rekonstruieren von Punktiermasken verwendet wird und als Code-Punktierbeschleuniger bezeichnet werden kann; und
Tabelle 1 gibt die Details von Berechnungen zum Auffinden der Komprimierungsverhältnisse an, die von einem Komprimierungsverfahren gemäß der vorliegenden Erfindung erzielt werden.
BESCHREIBUNG DER KONKRETEN AUSFÜHRUNGSFORMEN
Ausführungsformen der vorliegenden Erfindung verwenden eine Komprimierung und Entkomprimierung, um den Speicher zu reduzieren, der in elektronischen Systemen oder auf integrierten Schaltungen zum Speichern einer Mehrzahl von Punktiermasken benötigt wird.
3 zeigt ein solches Verfahren zum Komprimieren und Entkomprimieren einer Punktiermaske. Es ist eine Punktiermaske Pi 302 mit einer Länge bzw. Anzahl von Bits n vorgesehen. Die Bits, welche die Punktiermaske Pi 302 ausmachen, werden dann in eine Serie von Codes Ci 304 komprimiert. Diese Komprimierung kann durch Eins-Lauflängenkomprimierung, Null-Lauflängenkomprimierung, oder eine jegliche andere, geeignete Komprimierungsmethode bewirkt werden. Bei einer Eins-Lauflängenkomprimierung wird beginnend mit dem ersten Bit der Punktiermaske Pi 302 die Anzahl von aufeinander folgenden Einsen in einer Serie in der Punktiermaske 302 gezählt, bis eine Null erreicht ist. Die Anzahl von gezählten Einsen wird dann als ein binäres Wort gespeichert. Dieser Vorgang wird mit dem nächsten Bit im Anschluss an die Null fortgesetzt, bis Bit n der Punktiermaske Pi 302 erreicht ist. Die Null-Lauflängenkomprimierung funktioniert auf ähnliche Weise, aber mit dem Unterschied, dass Nullen gezählt werden.
Wenn die Punktiermaske für die Verwendung benötigt wird, wird die komprimierte Punktiermaske 304 entkomprimiert, was in der Punktiermaske 306 resultiert, die gleich der Punktiermaske 302 ist. Je nachdem, welches Komprimierungsverfahren zum Komprimieren der Punktiermaske Pi 302 verwendet wurde, wird ein geeignetes Entkomprimierungsverfahren benötigt. Wenn beispielsweise eine Eins-Lauflängencodierung verwendet wurde, wird die Anzahl von aufeinander folgenden Einsen in einer Serie aus den gespeicherten binären Wörtern ausgelesen, und diese Anzahl von Einsen, gefolgt von einer abschließenden Null, wird beginnend mit dem ersten Bit sequentiell an die zu rekonstruierende Punktiermaske angehängt.
Die Länge dieser Punktiermasken, welche die gleiche Länge wie ihre entsprechenden Codewörter besitzen, variiert bei dem EDGE(Enhanced Data rate for GSM Evolution) GSM (Global System for Mobile)-Standard von ca. 500 Bits bis 1836 Bits. Die verschiedenen, vorliegend offen gelegten Ausführungsformen der vorliegenden Erfindung sind für Punktiermaskenlängen von weniger als 1000 Bits, von 1000 oder mehr Bits, oder 2000 oder mehr Bits, sowie für zukünftige Standards, von denen erwartet wird, dass sie Punktiermasken von 5000 Bits und mehr erfordern, anwendbar.
In verschiedenen Teilen der Welt werden unterschiedliche Drahtlosstandards verwendet. Beispielsweise ist GSM in Europa üblicher als in Nordamerika. Reisende zwischen den Kontinenten werden erwarten und wünschen, dass ihre drahtlosen Kommunikationsvorrichtungen auf jeder Station der Reise funktionieren. Daher wird sich der Bedarf an drahtlosen Kommunikationsvorrichtungen, die mit mehr als einem Standard funktionieren, in der Zukunft intensivieren. Die verschiedenen, vorliegend offen gelegten Ausführungsformen der vorliegenden Erfindung unterstützen einen, zwei, oder drei oder mehr solche Standards.
Außerdem erfordert jeder unterstützte Standard mehrere Punktiermasken. Verschiedene Ausführungsformen der vorliegenden Erfindung unterstützen weniger als 30 Punktiermasken oder 30 oder mehr Punktiermasken oder 40 oder mehr Punktiermasken. Auch eine Anzahl von mehr als 70 Punktiermasken kann von einer Ausführungsform der vorliegenden Erfindung unterstützt werden. Mit einer zunehmenden Anzahl von zu speichernden Punktiermasken werden auch insgesamt mehr Bits an Speicher benötigt. Ausführungsformen der vorliegenden Erfindung unterstützen das Speichern einer Gesamtanzahl von Punktiermaskenbits von weniger als 30k, oder 30k oder mehr. Eine Anzahl von Punktiermaskenbits von mindestens 100k wird ebenfalls unterstützt. Wie vorstehend festgestellt wurde, besteht die vorliegende Lösung einfach darin, diese Punktiermasken im Speicher abzulegen. Das Vorsehen von so viel Speicher auf einer integrierten VLSI-Schaltung, die auch eine Schaltungsanordnung für drahtlose Kommunikationen aufweist, erhöht die Kosten und die Größe jedoch stark. Jenseits eines bestimmten Punktes ist das Hinzufügen von ausreichendem Speicher für die Aufnahme von Masken für eine Mehrzahl von Standards nicht mehr praktikabel. Die vorliegende Erfindung stellt ein effizientes Verfahren und eine effiziente Vorrichtung zum Komprimieren dieser Punktiermasken und ihr Entkomprimieren für einen späteren Abruf zur Verfügung.
4 zeigt ein solches effizientes Verfahren zum Komprimieren von Punktiermasken für einen späteren Abruf gemäß der vorliegenden Erfindung. Es wird eine Punktiermaske Pi 310 mit n Bits vorgesehen. Es wird eine Anzahl k vorgesehen, wobei k größer als Eins, aber kleiner als n ist. Es ist höchst wahrscheinlich, dass k eine Beziehung zu der Coderate aufweist, wobei k ein ganzzahliges Mehrfaches des Kehrwertes der Coderate ist. Ein k zwischen 3 und 66 funktioniert gut für viele Standards, aber k kann auch ein Wert von 2 oder größer als 66 sein. Die letzten k Bits 320 der Punktiermaske 310 werden gestrichen. Eine Anzahl k von Null-Bits 330 wird vorne an der beschnittenen Punktiermaske angehängt, um die verzögerte Maske Fi 340 zu bilden. Als Alternative können die k Null-Bits 330 angehängt werden, bevor die zu streichenden Bits 320 gestrichen werden, oder das Anhängen der Null-Bits 330 kann in der Streichung der zu streichenden Bits 320 resultieren. Jedes Bit i, wobei i in der Punktiermaske Pi von 1 bis n geht, wird daraufhin mit dem entsprechenden Bit i in der verzögerten Punktiermaske Fi XOR-verarbeitet, was in einem Bit i in einer differentiellen Punktiermaske Di 350 resultiert. Als Alternative können die ersten k Bits der Punktiermaske Pi 310 direkt in die differentielle Punktiermaske Di 350 eingelesen werden, da bekannt ist, dass die ersten k Bits der Punktiermaske Pi 310 mit einer Null XOR-verarbeitet werden, was darin resultiert, dass die ersten k Bits der differentiellen Punktiermaske Di 350 gleich den ersten k Bits der Punktiermaske Pi 310 sind. Außerdem komprimiert eine Ausführungsform der vorliegenden Erfindung diese Bits nicht, so dass die ersten k Bits der Punktiermaske Pi 310 einfach unverändert gespeichert werden können, ohne Teil der differentiellen Punktiermaske Di 350 zu sein.
Aus dem Vorstehenden ist ersichtlich, dass die differentielle Punktiermaske Di = Pi für i = 1 bis k, und Di = Pi ⊕ Pi – k für i = k + 1 bis nist.
Sobald die differentielle Punktiermaske berechnet wurde, kann sie auf elektronischem Wege komprimiert und gespeichert werden. Die elektronische Speicherung kann mit einem Speicher, einem ROM, einer Mehrzahl von Flipflops und dergleichen vorgenommen werden. Die Komprimierung kann auf unterschiedliche Weisen vorgenommen werden. Ein Verfahren, das beim Komprimieren von differentiellen Punktiermasken gut funktioniert, verwendet die Null-Lauflängencodierung.
Die ersten k Bits der differentiellen Punktiermaske Di 350 – oder alternativ die ersten k Bits der Punktiermaske Pi 310, da sie die Gleichen sind – werden ohne Modifikation gespeichert. Beginnend mit dem k + 1 Bit und auf das n Bit der differentiellen Punktiermaske 350 hin gehend wird jede Null gezählt, bis eine Eins erreicht ist. Die Anzahl von Nullen wird im Speicher in einem Wort mit der Länge L gespeichert, das in der komprimierten differentiellen Punktiermaske 360 als Ci gezeigt ist. Wenn beispielsweise L = 11, würden 1024 Nullen gefolgt von einer Eins als 10000000000 gespeichert, und eine Eins ohne vorausgehende Nullen würde als 0000000000 gespeichert. Dieser Vorgang wird wiederholt, bis das n Bit der differentiellen Punktiermaske erreicht ist. Die komprimierte differentielle Punktiermaske kann dann auf elektronischem Wege gespeichert werden. Bei einer Ausführungsform enthält L eine ausreichende Anzahl von Bits zum Speichern der längsten Abfolge von Nullen in der differentiellen Punktiermaske Di 350.
5 ist ein konkretes Beispiel für das verallgemeinerte Verfahren von 4. Es ist eine 11 Bit-Punktiermaske Pi 410 gezeigt. Bei diesem Beispiel ist k = 3. Die grundlegende Punktiermaske, auch als die Primärmatrix bezeichnet, ist 101, und in diesem Fall ist sie modifiziert, indem die dritte Wiederholung dieser grundlegenden Maske durch eine 111 ersetzt ist. Die letzten k Bits 420 werden abgeschnitten, und k Bits werden vorne an die Punktiermaske 410 angehängt, um die verzögerte Punktiermaske 440 zu erstellen. Jedes Bit i in der Punktiermaske Pi 410 wird mit seinem entsprechenden Bit i in der verzögerten Punktiermaske Fi 440 XOR-verarbeitet, um die differentielle Punktiermaske Di 450 zu erzeugen. Beispielsweise wird das erste Bit in Pi 410, das eine Eins ist, mit dem ersten Bit in der verzögerten Punktiermaske Fi 440, das eine Null ist, XOR-verarbeitet, was in einer Eins als dem ersten Bit in der differentiellen Punktiermaske Di 450 resultiert. Das zweite Bit in Pi 410, das eine Null ist, wird mit dem zweiten Bit in der verzögerten Punktiermaske Fi 440, das auch eine Null ist, XOR-verarbeitet, was in einer Null als dem zweiten Bit in der differentiellen Punktiermaske Di 450 resultiert. Dies wird für alle Bits in der Punktiermaske Pi 410 fortgesetzt.
Gemäß der vorstehenden Beschreibung werden beginnend mit dem k + 1 oder vierten Bit Nullen gezählt, bis eine Eins erreicht ist. Sobald eine Eins erreicht ist, endet das Zählen; die Eins wird übersprungen, und das Zählen wird wieder aufgenommen, bis die nächste Eins erreicht ist. In diesem Fall werden beginnend mit dem vierten Bit vier Nullen gezählt, bis eine Eins erreicht ist 460. Nach dieser werden zwei Nullen gezählt, bis die nächste Eins erreicht ist 470. Die Vier und die Zwei werden als binäre Wörter der Länge L = 3 codiert, 480 bzw. 485. Die komprimierten Daten, die im ROM oder in einem anderen Speichertyp gespeichert sind, sind die ersten k Bits der Punktiermaske Pi und die zwei 3Bit-Wörter 480 und 485.
Es sollte angemerkt werden, dass die Punktiermaske bei diesem Beispiel nicht mit 001, sondern mit 00 enden würde, falls die Punktiermaske nur zehn anstatt elf Bits aufweisen würde. Diese beiden Strings ergeben bei Komprimierung jeweils einen Wert von 2, so dass eine offensichtliche Zweideutigkeit besteht. Die Zweideutigkeit wird jedoch aufgelöst, wenn die 2 zu 001 entkomprimiert wird, und da keine Stelle für die letzte zu speichernde 1 vorhanden ist, wird 001 einfach als 00 gespeichert.
6 zeigt den Abruf und die Rekonstruktion einer verallgemeinerten Punktiermaske gemäß der vorliegenden Erfindung. Daten Ai 510 werden aus dem Speicher abgerufen. Die Daten können in RAM, ROM, einem anderen Speicher, Flipflops und dergleichen gespeichert sein. Die ersten k Bits von Ai 510 umfassen die ersten k Bits der Punktiermaske Pi 530 (oder der differentiellen Punktiermaske Di). Komprimierte Wörter der Länge L, die als Bits Ci 515 gelesen werden, umfassen den Rest von Ai 510. Die komprimierten Wörter der Länge L werden entkomprimiert und als Bits k + 1 bis n der differentiellen Punktiermaske Di 520 eingelesen. Die Punktiermaske selbst wird daraufhin auf die folgende Weise rekonstruiert. Die ersten k Bits der komprimierten differentiellen Punktiermaske Ai 510 werden als die ersten k Bits der Punktiermaske Pi 530 eingelesen. Das erste Bit der Punktiermaske Pi 530 wird mit dem k + 1 Bit der differentiellen Punktiermaske XOR-verarbeitet, wobei das Resultat das k + 1 Bit der Punktiermaske 550 ist. Dieser Vorgang wird Bit um Bit wiederholt, bis das n – k Bit der Punktiermaske 530 mit dem n Bit der differentiellen Punktiermaske 520 XOR-verarbeitet wird, was in dem n Bit 560 der Punktiermaske 530 resultiert. Die Punktiermaske 530 wird daher unter Verwendung der differentiellen Punktiermaske 520 und von früher extrahierten Bits in der Punktiermaske 530 selbst aus der differentiellen Punktiermaske extrahiert.
Aus dem Vorstehenden ist ersichtlich, dass die Punktiermaske 530 Pi = Ai für i = 1 bis k, und Pi = Di ⊕ Pi – k für i = k + 1 bis nist, wobei Pi die Punktiermaske Pi 530 ist, Ai die komprimierte differentielle Punktiermaske 510 ist, und Di die differentielle Punktiermaske 520 ist.
7 ist ein konkretes Beispiel für das verallgemeinerte Verfahren, das in 6 gezeigt ist. Gezeigt sind die ersten 9 Bits einer komprimierten differentiellen Punktiermaske Ai 610. Bei diesem Beispiel ist k = 3 und L = 3. Diese zwei Werte müssen für jede komprimierte differentielle Punktiermaske bekannt sein und werden bei einer Ausführungsform der vorliegenden Erfindung unter Steuerung durch einen Digitalsignalprozessor (DSP) in Steuerregistern gespeichert. Die ersten k Bits der komprimierten differentiellen Punktiermaske Ai 610 werden in die Punktiermaske Pi 650 eingelesen. Beginnend mit dem k + 1 (vierten) Bit in der komprimierten differentiellen Punktiermaske Ai 610 werden die nächsten L Bits als ein binäres Wort 620 genommen. Die differentielle Punktiermaske kann unter Verwendung der Null-Lauflängenkomprimierung oder anderer Komprimierungsarten komprimiert worden sein. Wenn die differentielle Punktiermaske ursprünglich unter Verwendung der Null-Lauflängencodierung komprimiert wurde, wird ein String von Nullen gleich dem Wert des binären Wortes, das mit einer Eins 625 endet, bei der k + 1 Position beginnend an die differentielle Punktiermaske angehängt. Die L = 3 Bits beginnend mit dem k + 1 Bit der komprimierten differentiellen Punktiermaske Ai 610 sind bei diesem Beispiel 100. Bei diesem Beispiel werden die Codewörter der Länge L auf eine einfache binäre Weise codiert, wobei das rechte Bit einen Wert von Eins, das mittlere Bit einen Wert von Zwei, und das linke Bit einen Wert von Vier besitzt. Daher kann die 100 in einen Wert von 1(4) + 0(2) + 0(1) = 4 übersetzt werden. Andere Codierungstypen – Gray-Codierung, Thermometercodierung und dergleichen – können alternativ verwendet werden. Die 100 wird somit in einen String von vier Nullen konvertiert, der mit einer Eins 625 endet. Die nächsten L Bits 630 von Ai 610 sind 010 mit einem Wert von Zwei, und werden daher in einen String von zwei Nullen, gefolgt von einer Eins 635, konvertiert. Auf diese Weise wird die differentielle Punktiermaske Di 640 entkomprimiert.
Die Punktiermaske 650 wird im allgemeinen Fall auf die oben beschriebene Weise von der differentiellen Punktiermaske 640 abgeleitet, was in 6 gezeigt wurde. Das Bit in der k + 1 (vierten) Position 672 der differentiellen Punktiermaske Di 640, eine Null, wird mit dem (k + 1) – k (ersten) Bit 674 der Punktiermaske 650, einer Eins, XOR-verarbeitet 670, was in einer Eins in der k + 1 (vierten) Position 676 in der Punktiermaske Pi 650 resultiert. Dies wird fortgesetzt, bis das Bit in der n (elften) Position 682 der differentiellen Punktiermaske Di 640, eine Eins, mit dem Bit in der n – k (achten) Position 684 der Punktiermaske Pi 650, ebenfalls einer Eins, XOR- verarbeitet wird, was in einer Null resultiert, die in der n (elften) Position 686 in die Punktiermaske Pi 650 eingesetzt wird.
8 ist ein Ablaufdiagramm eines Verfahrens zur Komprimierung für eine Punktiermaske gemäß der vorliegenden Erfindung. Beginnend mit der Punktiermaske Pi in Schritt 710 werden die letzten k Bits, Bits Pn – k + 1 bis Pn, in Schritt 720 gestrichen. K Nullen werden in Schritt 730 vorne an der beschnittenen Punktiermaske angehängt, um eine verzögerte Punktiermaske zu erstellen. Für den Fachmann ist ersichtlich, dass diese zwei Schritte vertauscht werden können. Beispielsweise könnten die k Nullen in ein Schieberegister verschoben werden, das n Bits lang ist und die Punktiermaske enthält. Die letzten k Bits würden aus dem Schieberegister hinaus verschoben und auf diese Weise gestrichen.
Die verzögerte Punktiermaske und die ursprüngliche Punktiermaske werden daraufhin in Schritt 740 XOR-verarbeitet, wodurch eine differentielle Punktiermaske erzeugt wird. Die ersten k Bits der Punktiermaske und die ersten k Bits der differentiellen Punktiermaske sind gleich, da eine XOR-Verarbeitung eines jeglichen logischen Zustands mit einer Null ein Resultat mit diesem gleichen logischen Zustand ergibt. Die übrigen Bits k + 1 bis n können dann komprimiert werden, und das gesamte Resultat kann auf elektronischem Wege gespeichert werden.
Die elektronische Speicherung kann in einem IC-Speicher wie etwa einem RAM, einem ROM, einem SRAM, einem Flash-EPROM, einer Anordnung von Flipflops und dergleichen stattfinden. Der IC-Speicher kann eine separate Vorrichtung oder vorzugsweise auch Teil einer integrierten Schaltung für die drahtlose Kommunikation sein. Die integrierte Schaltung für die drahtlose Kommunikation umfasst bevorzugt mindestens einen Abschnitt eines Empfangs- und Sendepfades auf dem gleichen Substrat, aus dem auch die integrierte Schaltung besteht. Die integrierte Schaltung kann stattdessen nur mindestens einen Abschnitt eines Empfangspfades oder mindestens einen Abschnitt eines Sendepfades aufweisen. Der Empfangspfad oder ein Abschnitt davon ist für den Empfang von Funksignalen bestimmt, und der Sendepfad oder ein Abschnitt davon ist für die Übertragung von Funksignalen an einen anderen Empfänger bestimmt. Der Abschnitt des Empfangspfades auf der integrierten Schaltung, der den Empfangspfad vollständig oder teilweise umfassen kann, kann jeweils die Gesamtheit oder einen Abschnitt von einem oder mehreren der folgenden umfassen: Verstärker, Begrenzerschaltung, Bandpassfilter, Tiefpass filter, Hochpassfilter, Mischer, Spiegelselektionsmischer, Diskriminator, Mehrphasenfilter und dergleichen. Der Abschnitt des Sendepfades auf der integrierten Schaltung, der den Sendepfad vollständig oder teilweise umfassen kann, kann jeweils die Gesamtheit oder einen Abschnitt von einem oder mehreren der folgenden umfassen: VCO (Voltage Controlled Oscillator; spannungsgesteuerter Oszillator), DAC (Digital to Analog Converter; D/A-Wandler), Bandpassfilter, Tiefpassfilter, Hochpassfilter, Antialiasing-Filter, Mehrphasenfilter, Mischer, Spiegelselektionsmischer, und dergleichen.
Die Komprimierung kann mithilfe mehrerer Einrichtungen bewirkt werden; eine Ausführungsform der vorliegenden Erfindung verwendet die Null-Lauflängencodierung. Bei der Null-Lauflängencodierung werden beginnend mit dem k + 1 Bit der differentiellen Punktiermaske die Nullen gezählt, bis eine Eins erreicht ist. Die Anzahl von Nullen wird in ein binäres Wort der Länge L übersetzt. Diese Übersetzung kann mit gewöhnlicher binärer Gewichtung, Gray-Codierung oder dergleichen bewirkt werden. Nachdem die erste Eins erreicht ist, wird der Zähler zurückgesetzt, und im Anschluss an die Eins werden wieder Nullen gezählt, bis eine zweite Eins erreicht ist. Dieses Muster wird fortgesetzt, bis Bit n der differentiellen Punktiermaske erreicht ist.
Die Null-Lauflängenkomprimierung funktioniert bei der vorliegenden Erfindung aus den folgenden Gründen gut. Gemäß der vorstehenden Beschreibung werden die Daten, die von einem Sender an einen Empfänger gesendet werden sollen, codiert. Die Codierung wird durchgeführt, indem jedes Bit durch eine Anzahl von Chips ersetzt wird und diese Chips dann an den Empfänger gesendet werden. Die Anzahl von Chips pro Bit wird als die Codierrate bezeichnet. Ein Codierer, der 3 Chips pro Bit ersetzt, arbeitet mit einer Coderate von 1/3. K ist typischerweise ein ganzzahliges Vielfaches der Anzahl von Chips pro Bit. Ferner tendiert die Punktiermaske dazu, einem Muster zu folgen, das in gewissem Maße auf der Anzahl von Chips pro Bit beruht, und auch auf Zahl k beruht. Tatsächlich wird k so gewählt, dass es das Grundmuster umfasst, aus dem die Punktiermaske besteht. Wie vorstehend erwähnt wurde, wird dieses Grundmuster als die Primärmatrix bezeichnet. Wenn die Punktiermaske aus Wiederholungen der Primärmatrix besteht, und k so eingestellt ist, dass es gleich der Anzahl von Bits in der Primärmatrix ist, besteht die Punktiermaske aus einer Serie von Bits, wobei die ersten k Bits beginnend an den k + 1, 2k + 1 usw. Bits bis zum Bit n einfach wiederholt werden. In diesem Fall ist die differentielle Punktiermaske die ersten k Bits der Punktiermaske, gefolgt von nur Nullen. Variationen in der Wiederholung des Musters der ersten k Bits können als zwei Einsen erscheinen, die in der differentiellen Punktiermaske um k Positionen voneinander beabstandet sind. Jede entspricht einem Wort, das für eine spätere Entkomprimierung auf elektronischem Wege gespeichert wird.
Hier ist es jedoch wichtig anzumerken, dass jede Variation zwischen dem Muster der ersten k Bits und den Bits k + 1 bis 2k und 2k + 1 bis 3k usw. in zwei Codewörtern der Länge L resultieren kann, die daher auf elektronischem Wege gespeichert werden müssen. Angesichts dieser Tatsache ist es selbstverständlich, dass einige Punktiermasken sich nicht gut für eine Komprimierung eignen und sich tatsächlich auf eine Länge von mehr als n Bits erweitern können, wobei n die Anzahl von Bits in der ursprünglichen Punktiermaske ist. Daher kann ein zusätzliches Flag-Bit mit jeder komprimierten Punktiermaske gespeichert werden, wobei eine Polarität dieses Bits anzeigt, dass die Punktiermaske nicht komprimiert wurde, sondern einfach ohne Modifikation im Speicher abgelegt wurde.
Die Tatsache, dass die Primärmatrix der ersten k Bits eine Tendenz besitzt, sich über die gesamte Länge einer Punktiermaske zu wiederholen, bedeutet, dass Punktiermasken auch anderen Komprimierungsmethoden zugänglich sind. Ein solches Verfahren wäre es, einen Codebuch-Lösungsansatz zu verwenden. Jedes eindeutige Muster von k Bits, 0 bis k, k + 1 bis 2k usw., das zum Konstruieren der Punktiermaske benötigt wird, ist im Speicher abgelegt. Jedem k Bit-Wort wird dann ein Code zugeordnet, z. B. ein Huffman-Code. Die Codes werden daraufhin im Speicher abgelegt. Wenn eine Punktiermaske benötigt wird, werden die Codes abgerufen, und die entsprechenden k Bit-Wörter werden aus dem Speicher gezogen und so verkettet, dass sie die Punktiermaske bilden.
9 ist ein Ablaufdiagramm eines Verfahrens zur Entkomprimierung gemäß der vorliegenden Erfindung, das dieses Konzept beinhaltet. Der erste Schritt 810 ist es, die Polarität der Flag zu überprüfen, um zu sehen, ob die Punktiermaske komprimiert wurde oder nicht. Wenn die Polarität anzeigt, dass die Punktiermaske nicht komprimiert wurde, wird die gesamte Punktiermaske in Schritt 820 aus dem Speicher ausgelesen, und der Vorgang endet, Schritt 890. Wenn angezeigt wird, dass die Punktiermaske komprimiert wurde, werden die ersten k Bits einer differentiellen Punktiermaske aus dem Speicher 830 ausgelesen und in Schritt 840 in einem Punk tiermaskenregister platziert. Die komprimierten Codewörter mit der Länge L werden in Schritt 850 Wort für Wort rückgelesen, und in Schritt 855 werden die Codewörter entkomprimiert, um die differentielle Punktiermaske zu vervollständigen.
Eine Ausführungsform der vorliegenden Erfindung verwendet die Null-Lauflängendecodierung, um die Codewörter zu entkomprimieren. Bei der Null-Lauflängendecodierung wird dem zu decodierenden Wort ein Wert gegeben. Bei einer Ausführungsform der vorliegenden Erfindung beruht der gegebene Wert auf der binären Gewichtung der Bits in dem Wort. Beispielsweise hat eine Eins im LSB (Least Significant Bit; niedrigstwertiges Bit) ein Gewicht von Eins, die Eins in der nächsten Position hat ein Gewicht von Zwei, daraufhin 4, dann 8 und so weiter, entsprechend der Formel 2^n–1, wobei n die Bitstellenposition beginnend mit Eins für das LSB ist und für jede Stelle um Eins inkrementiert wird. Andere Einrichtungen können verwendet werden, um den Codewörtern Werte zuzuordnen, wie etwa Gray-Code und dergleichen. Eine diesem Wert entsprechende Anzahl von Nullen, gefolgt von einer abschließenden Eins, wird dann beginnend mit der k + 1 Position in der differentiellen Punktiermaske an die differentielle Punktiermaske angehängt. Dieses Muster wird daraufhin wiederholt, bis alle Codewörter, aus denen die gespeicherte differentielle Punktiermaske besteht, rückgelesen und entkomprimiert wurden.
Die Punktiermaske kann daraufhin auf die folgende Weise von der differentiellen Punktiermaske abgeleitet werden. Ein Zähler mit einem Zählwert i kann auf 1 zurückgesetzt werden. Das k + i Bit aus der differentiellen Punktiermaske wird abgerufen 865, und ebenso das i Bit der Punktiermaske selbst in Schritt 870. Das k + 1 Bit der differentiellen Punktiermaske wird daraufhin mit dem i Bit der Punktiermaske XOR-verarbeitet, und das Ergebnis davon wird in der Punktiermaske an der Position k + 1 gespeichert. Dieser Vorgang wird in Schritt 880 fortgesetzt, bis i gleich n – k + 1 ist, wonach der Vorgang bei Schritt 890 endet. Falls i weniger als n – k + 1 ist, wobei n die Länge der Punktiermaske ist, die gleich derjenigen der differentiellen Punktiermaske ist, wird i in Schritt 885 um Eins inkrementiert, und die passenden Werte werden in den Schritten 865 und 870 wieder abgerufen. Es ist wichtig anzumerken, dass der Vorgang des Rekonstruierens der Punktiermaske aus der differentiellen Punktiermaske die Verwendung der differentiellen Punktiermaske und von vorausgehend berechneten Bits in der Punktiermaske selbst erfordert.
Eine Vorrichtung gemäß der vorliegenden Erfindung, welche dieses letztere Konzept anwendet, ist in 10 in Form eines Blockdiagramms gezeigt. Diese Vorrichtung kann als ein Code-Punktierbeschleuniger bezeichnet werden und ist Teil einer integrierten Schaltung für die drahtlose Kommunikation. Diese Vorrichtung kann, falls erforderlich, eine Punktiermaske rekonstruieren oder erzeugen, und kann diese Maske dann verwenden, um Bits aus einem Codewort zu punktieren bzw. zu streichen, und kann Löschungen in einen Empfangsdaten-Bitstrom einsetzen. Die Vorrichtung umfasst einen Daten-ROM 910, einen Lauflängendecoder 920, einen Differentialoperator 930, ein Punktiermaskenregister 940, einen Codierer 960, einen Sendepunktierlogikblock 970, einen Decoder 975, einen Empfangspunktierlogikblock 980, einen DSP 990, und Steuerregister 995. Der Daten-ROM 910 weist einen Ausgang 912 auf, der mit einem Schalter 915 gekoppelt ist. Der Daten-ROM kann alternativ ein beliebiger Typ eines Halbleiterspeichers sein, wie etwa ein RAM, Flipflops, EPROM, Flash-EPROM, SRAM oder dergleichen. Der Schalter besitzt zwei Positionen für die Kopplung mit entweder einem Eingang eines Lauflängendecoders 920 auf der Leitung 917, oder mit einer Bypassleitung 918, die mit einem ersten Eingang des Punktiermaskenregisters 940 gekoppelt ist. Der Lauflängendecoder 920 hat einen Eingang, der mit einer Schaltposition des Schalters 915 gekoppelt ist, und einen Ausgang, der mit einem ersten Eingang eines Differentialoperators 930 durch die Leitung 925 gekoppelt ist. Der Differentialoperator 930 hat ferner einen zweiten Eingang, der mit dem Punktiermaskenregister 940 durch die Leitung 935 gekoppelt ist, und einen Ausgang, der durch die Leitung 937 auch mit einem zweiten Eingang der Punktiermaskenregister gekoppelt ist. Das Punktiermaskenregister 940 hat auch einen zweiten Ausgang, der durch die Leitung 950 mit einem zweiten Eingang der Sendepunktierlogik 970 und ebenfalls durch die Leitung 950 mit einem zweiten Eingang der Empfangspunktierlogik 980 gekoppelt ist.
Die Empfangspunktierlogik 980 hat einen ersten Eingang 985, an dem Empfangsdaten Ri 986 empfangen werden, sowie einen Ausgang, der mit dem Eingang des Decoders 975 auf der Leitung 987 gekoppelt ist. Der Decoder 975 hat ferner einen Ausgang 974, an dem die empfangenen Anwenderdaten Ui 973 ausgegeben werden. Die Sendepunktierlogik 970 hat einen Ausgang 972, an dem die Sendepunktierlogik 970 zu übertragende Daten 973 ausgibt, sowie einen ersten Eingang, der durch die Leitung 965 mit dem Ausgang eines Codierers 960 gekoppelt ist. Der Codierer hat ferner einen Eingang 955, an dem er Anwenderdaten Ti 954 empfängt. Die Steuerregister 995 unterliegen der Steuerung durch den DSP 990.
Es folgt eine Betriebsweise gemäß der vorliegenden Erfindung. Der DSP 990 erkennt, dass eine neue Punktiermaske zur Verwendung beim Übertragen von Daten benötigt wird. Eine Flag in den Steuerregistern 995 wird überprüft, um zu sehen, ob die Punktiermaske komprimiert wurde. Wenn die benötigte Punktiermaske nicht komprimiert wurde, koppelt der Schalter 915 den Ausgang 912 des Daten-ROM 910 mit der Bypassleitung 918, und die gesamte Punktiermaske wird auf die Bypassleitung 918 ausgelesen und im Punktiermaskenregister 940 gespeichert.
Wenn die Flag im Steuerregister 995 anzeigt, dass die Maske komprimiert wurde, werden die Startadresse der Punktiermaske sowie die Parameter k, L und M für die benötigte Punktiermaske aus den Steuerregistern 995 ausgelesen. Der Schalter 915 koppelt den Ausgang 912 des Daten-ROM 910 mit der Bypassleitung 918, und die ersten k Bits werden in das Punktiermaskenregister 940 geladen. Der Schalter 915 koppelt dann den Ausgang 912 des Daten-ROM 910 mit dem Eingang des Lauflängendecoders 920. Ein binäres Codewort mit der Länge L wird daraufhin in den Lauflängendecoder eingelesen, und eine Anzahl von Nullen, gefolgt von einer Eins, wobei die Anzahl von Nullen gleich dem Wert des Codewortes mit der Länge L ist. Eine Ausführungsform gemäß der vorliegenden Erfindung kann das Codewort in einen Abwärtszähler laden und für jede Abwärtszählung eine Null ausgeben, bis ein Zählwert Null erreicht ist, woraufhin eine Eins ausgegeben wird und ein neues Codewort in den Lauflängendecoder geladen wird. Das Ausgangssignal des Lauflängendecoders 920 ist auf der Leitung 925 und stellt die differentielle Punktiermaske dar. Die differentielle Punktiermaske tritt daher, beginnend mit dem Bit in der k + 1 Position, Bit um Bit auf der Leitung 925 in den ersten Eingang des Differentialoperators ein. Es wird angemerkt, dass die ersten k Bits den Lauflängendecoder 920 sowie den Differentialoperator 920 unter Verwendung der Bypassleitung 918 umgangen haben und sich daher bereits im Punktiermaskenregister 940 befinden. Der Differentialoperator ruft auch das (k + 1) – k bzw. erste Bit der Punktiermaske aus dem Punktiermaskenregister 940 auf der Leitung 935 ab. Daraufhin nimmt der Differentialoperator das XOR des k + 1 Bit der differentiellen Punktiermaske an seinem ersten Eingang auf der Leitung 925, und das erste Bit der Punktiermaske auf seiner zweiten Eingangsleitung 935 aus dem Punktiermaskenregister, und gibt das Ergebnis an seinem Ausgang 937 aus, damit es an die Punktiermaskenposition k + 1 im Punktiermaskenregister 940 eingegeben wird.
Der Lauflängendecoder 920, der Differentialoperator 930 und das Punktiermaskenregister 940 können zusammen getaktet sein. In jedem Taktzyklus findet daher jeweils folgendes statt: der Abwärtszähler im Lauflängendecoder zählt um Eins abwärts, der Differentialoperator ruft ein Bit aus dem Punktiermaskenregister ab und führt eine XOR-Operation durch, und das Punktiermaskenregister gibt das Resultat aus dem vorherigen Taktzyklus in die Punktiermaske ein. Dies wird fortgesetzt, bis der Abwärtszähler im Lauflängendecoder 920 Null erreicht; zu diesem Zeitpunkt wird ein zweiter Zähler um Eins inkrementiert. Der Wert dieses zweiten Zählers wird überprüft, um zu sehen, ob er den Wert M erreicht hat. Falls nicht, wird das nächste Codewort mit der Länge L in den Lauflängendecoder 920 eingegeben, und der Abwärtszählvorgang geht weiter. Wenn der Abwärtszähler M Mal abwärts gezählt hat und die letzte abschließende Eins verarbeitet wurde, ist die Punktiermaske vollständig.
Entweder während oder nach der Rekonstruktion der Punktiermaske im Punktiermaskenregister 940 kann die Punktiermaske entweder Bit um Bit oder auf einmal an die Sendepunktierlogik 970 gesendet werden. Die Anwenderdaten Ti 954 werden auf der Leitung 955 platziert, um von dem Codierer 960 codiert zu werden. Der Codierer 960 ist typischerweise ein Faltungscodierer, jedoch können in verschiedenen Ausführungsformen der vorliegenden Erfindung andere Codierer verwendet werden. Der Codierer 960 kann jedes Bit von Anwenderdaten Ti durch eine bestimmte Anzahl von als Chips bezeichneten Bits ersetzen, so dass er auf der Leitung 965 codierte Daten für die Eingabe an den ersten Eingang der Sendepunktierlogik 970 ausgibt. Die codierten Daten auf der Leitung 965, das Codewort, und die Punktiermaske im Punktiermaskenregister 940 bestehen beide aus der gleichen Anzahl von Bits n. Die Sendepunktierlogik 970 löscht bzw. streicht daraufhin jedes Bit i in den codierten Daten auf der Leitung 965, das einer Null in der i Position in der Punktiermaske im Punktiermaskenregister 940 entspricht, und gibt jedes Bit i in den codierten Daten, das einer Eins in der i Position in der Punktiermaske im Punktiermaskenregister 940 entspricht, auf der Leitung 965 aus.
Als Alternative oder gleichzeitig, entweder während oder nach der Rekonstruktion der Punktiermaske im Punktiermaskenregister 940, kann die Punktiermaske entweder Bit um Bit oder auf einmal auf der Leitung 950 an den zweiten Eingang der Empfangspunktierlogik 980 gesendet werden. Die Empfangsdaten Ri 986 werden auf der Leitung 985 empfangen und an den ersten Eingang der Empfangspunktierlogik 980 eingegeben. Die Empfangspunktierlogik betrachtet die Punktiermaske auf der Leitung 950 und die Empfangsdaten Ri 986 auf der Leitung 985 jeweils Bit um Bit. Wenn das aktuelle Bit i in der Punktiermaske eine Eins ist, wird das aktuelle Bit der Empfangsdaten Ri 986 an den Decoder auf der Leitung 987 ausgegeben. Wenn das aktuelle Bit i in der Punktiermaske eine Null ist, wird eine Löschung in die Empfangsdaten Ri 986 eingesetzt, und das nächste Bit in der Punktiermaske im Punktiermaskenregister 940 wird überprüft. Dieser Vorgang wird für alle n-x Bits der Empfangsdaten Ri fortgesetzt, wobei n die Anzahl von Bits in den codierten Anwenderdaten sowie der Punktiermaske ist, und x die Anzahl von Löschungen oder Streichungen ist, die der gleichen Anzahl von Nullen in der Punktiermaske entspricht.
Wie vorstehend beschrieben wurde, gibt das von dem DSP geschriebene Steuerregister den Punktiermodus an. Das Steuerregister muss folgendes speichern: die Länge n der Punktiermaske, die gleich dem Codewort ist, die Länge k, die Länge L der komprimierten Wörter, die Komprimierungsflag, die anzeigt, ob die Punktiermaske komprimiert wurde, und die ROM-Startadresse der gespeicherten Punktiermaske.
Tabelle 1 ist eine Zusammenfassung der Komprimierungsverhältnisse, die unter Verwendung einiger der vorstehend beschriebenen Verfahren tatsächlich erzielt werden. Die erste Spalte 1010 führt einige Moduskennungen in EGPRS-, GPRS- und GSM-Systemen auf, welche die zu verwendende Maske definieren. Die Asterisken bezeichnen Duplikateinträge, wobei der Duplikateintrag unter Verwendung eines größeren k als der entsprechenden Eintrag ohne Asterisk komprimiert wird. Beispielsweise wurde der zweite Eintrag CS-2* unter Verwendung von k = 48 komprimiert, während CS-2, die gleiche Punktiermaske, unter Verwendung von k = 4 komprimiert wurde. Der Nachteil eines größeren k ist es, dass die Komplexität der Hardware etwas zunehmen kann und die Verzögerung bei der Differentialoperation wesentlich länger ist.
Die Punktiermaskenlänge n gemäß der Definition in dem geeigneten Standard ist in Spalte 1020 angegeben. Die Punktiermaskenlänge in Wörtern ist einfach n/16, aufgerundet auf die nächsthöhere ganze Zahl (d. h. der Deckelwert von n/16), und ist in Spalte 1030 angegeben. Dies ist die Anzahl von Wörtern, welche die Punktiermaske in einem 16 Bit breiten Speicher einnehmen würde, falls keine Komprimierung verwendet würde. Das k für jede Punktiermaske ist in Spalte 1040 angegeben, und wie vorstehend beschrieben wurde, sind für einige Punktiermasken die Resultate von mehr als einem k angegeben. Wie weiter oben erwähnt wurde, gibt es in den verschiedenen Standards keine Angabe eines Wertes für k. Stattdessen ist k ein Parameter, der auf der Grundlage von Entwurfserwägungen für jede Punktiermaske nach Untersuchung der Primärmatrix und der Punktiermaske selbst gewählt wird. Ein Computerprogramm oder dergleichen, das einfach jedes k von 1 bis n oder von 2 bis n/2 oder einen anderen Bereich durchprobiert und die Komprimierung berechnet, kann als Alternative verwendet werden.
Die Codelänge L für jede Punktiermaske ist in Spalte 1045 angegeben. L ist einfach die kleinste binäre Zahl, welche die größte Lauflänge von Nullen in der differentiellen Punktiermaske entsprechend der zu komprimierenden Punktiermaske beschreibt. Die Anzahl von Codewörtern, die benötigt wird, um die Bits k + 1 bis n der differentiellen Punktiermaske entsprechend der zu komprimierenden Punktiermaske zu beschreiben, ist in Spalte 1050 aufgeführt.
Beispielsweise weist der vierte Eintrag CS-3 N = 676, k = 6, L = 10, und M = 1 auf. Gemäß der vorstehenden Beschreibung werden die ersten 6 Bits gespeichert, so dass die nächsten 670 für eine Komprimierung verbleiben. In diesem Fall ist die Punktiermaske eben diese 6 Primärmatrixbits, die 112 Mal wiederholt werden, gefolgt von den ersten vier Bits, die ein weiteres Mal wiederholt werden. Die differentielle Punktiermaske besteht von Bits 7 bis 676 insgesamt aus Nullen und kann als ein Wort mit einer Länge von 10 Bits komprimiert werden. (2¹⁰ = 1024, was groß genug ist, um den Wert 670 zu beschreiben.) Daher muss L 10 sein, und M kann Eins sein, da nur ein Wort benötigt wird. Es ist anzumerken, dass k wie bei diesem Beispiel nicht so definiert zu werden braucht, dass n ein ganzzahliges Mehrfaches von k ist.
Der insgesamt benötigte Speicher ist in Spalte 1055 aufgeführt und wird durch Summieren der Anzahl von Bits berechnet, die zum Speichern von k erforderlich sind, zusammen mit der M Anzahl von L Bitwörtern. In Gleichungsform ist die Anzahl von erforderlichen Bits k + L mal M. Die Anzahl von Wörtern im Speicher, die zum Speichern der Informationen benötigt werden, ist der Wert in 1055 geteilt durch 16, wiederum auf die nächsthöhere ganze Zahl aufgerundet, und ist in Spalte 1060 gezeigt. Das Komprimierungsverhältnis kann daher aufgefunden werden, indem man die zum Speichern der unkomprimierten Maske benötigte Anzahl von Wörtern, Spalte 1030, durch die Anzahl von zum Speichern der komprimierten Maske benötigten Wörter, Spalte 1060, teilt. Das Resultat dieser Berechnung ist in Spalte 1065 zu linden.
Das kombinierte Gesamtkomprimierungsverhältnis kann berechnet werden, indem man die zum Speicher der nicht komprimierten Maske benötigte Anzahl von Wörtern für jeden Eintrag in Spalte 1030 addiert und durch die Gesamtanzahl von zum Speichern der komprimierten Maske benötigten Wörtern für jeden Eintrag in Spalte 1060 teilt. Da einige Masken zwei Mal komprimiert wurden, sind die Einträge mit dem größeren k, die mit einem Asterisken bezeichnet sind, in der Zeile Gesamt* 1070 gezählt, und die Einträge mit dem kleineren k, ohne Asterisk, sind in der Zeile Gesamt 1080 gezählt.
Die Komprimierungsverhältnisse sind insgesamt 14.64 mit Einträgen mit einem großen k und 12.46 mit Einträgen mit einem kleinen k. Dies zeigt, dass ein Komprimierungsverfahren gemäß der vorliegenden Erfindung sehr gut funktioniert. Diese Reduzierung der Speichererfordernisse spart Platz auf einer integrierten Schaltung und verringert dadurch ihre Kosten. Der Overhead zur Verwendung dieser Komprimierung ist eine Vorrichtung, die als ein Code-Punktierbeschleuniger bezeichnet werden kann, und ein Speicher, der sich in einem Steuerregister befinden kann, für k, L, M, und die Startadresse der Punktiermaske. TABELLE 1 ROM-Anforderungen für die Punktierung im EGPRS-, GPRS- und GSM-Datenmodus

* Bezeichnet den Fall, in dem Mehrfache der grundlegenden Punktiermatrix als die grundlegende Periode K verwendet werden.

Claims

Verfahren zum Komprimieren von Punktiermaskeninformationen zur Verwendung in einem drahtlosen Kommunikationssystem, dadurch gekennzeichnet, dass das Verfahren umfasst: Erstellen einer verzögerten Punktiermaske (340) mittels: Löschen von letzten k Bits (320) einer Punktiermaske (310), wobei k eine ganze Zahl ist, die größer als Eins und kleiner als n ist, wobei n eine Länge der Punktiermaske (310) ist; und Anhängen von k Nullen (330) an einen Anfang der Punktiermaske (310); Erstellen einer differentiellen Punktiermaske (350) mittels XOR-Verarbeitung der verzögerten Punktiermaske (340) mit der Punktiermaske (310); und Komprimieren der differentiellen Punktiermaske (350).
Verfahren nach Anspruch 1, welches ferner umfasst: Speichern der differentiellen Punktiermaske (350) in einem Halbleiterspeicher.
Verfahren nach Anspruch 1, wobei das Komprimieren der differentiellen Punktiermaske (350) folgendes umfasst: Beginnen mit einem k + 1 Bit der differentiellen Punktiermaske (350), Zählen einer Anzahl von Nullen, bis eine Eins erreicht ist; und Speichern der Anzahl von Nullen im Speicher.
Verfahren nach Anspruch 1, wobei die Länge der Punktiermaske mindestens 1000 Bits beträgt.
Verfahren nach Anspruch 1, wobei die Länge der Punktiermaske mindestens 2000 Bits beträgt.
Verfahren nach Anspruch 1, wobei Punktiermasken aus mindestens zwei Kommunikationsstandards komprimiert werden.
Verfahren nach Anspruch 1, wobei mindestens 30 Punktiermasken komprimiert werden.
Verfahren zum Entkomprimieren und Verwenden einer Punktiermaske zur Verwendung in einem drahtlosen Kommunikationssystem, dadurch gekennzeichnet, dass das Verfahren umfasst: Vorsehen einer komprimierten differentiellen Punktiermaske (510); Entkomprimieren der komprimierten differentiellen Punktiermaske (510); Speichern von ersten k Bits der entkomprimierten differentiellen Punktiermaske (520) als erste k Bits einer entkomprimierten Punktiermaske (530), wobei k eine ganze Zahl ist, die größer als Eins und kleiner als n ist, wobei n eine Länge der Punktiermaske ist; Beginnen mit einem k + 1 Bit der entkomprimierten differentiellen Punktiermaske (520); XOR-Verarbeitung des k + 1 Bits der entkomprimierten differentiellen Punktiermaske (520) mit einem ersten Bit der entkomprimierten differentiellen Punktiermaske (520), so dass sich ein Produkt ergibt; und Speichern des Produktes als k + 1 Bit der entkomprimierten Punktiermaske (530); Fortfahren mit jedem Bit in der entkomprimierten differentiellen Punktiermaske (520), bis ein letztes Bit erreicht ist; XOR-Verarbeitung von jedem k + i Bit der entkomprimierten differentiellen Punktiermaske (520) mit einem i Bit der entkomprimierten Punktiermaske (530), so dass sich ein Produkt ergibt; und Speichern des Produktes als das k + i Bit der entkomprimierten Punktiermaske (530).
Verfahren nach Anspruch 8, wobei die Länge der entkomprimierten Punktiermaske mindestens 1000 Bits beträgt.
Verfahren nach Anspruch 8, wobei die Länge der entkomprimierten Punktiermaske mindestens 2000 Bits beträgt.
Verfahren nach Anspruch 8, wobei Punktiermasken aus mindestens zwei Kommunikationsstandards komprimiert werden.
Verfahren nach Anspruch 8, wobei mindestens 30 Punktiermasken komprimiert werden.
Verfahren nach Anspruch 8, wobei das Entkomprimieren der komprimierten differentiellen Punktiermaske (510) unter Verwendung einer Lauflängendecodierung durchgeführt wird.
Verfahren nach Anspruch 13, wobei die Lauflängendecodierung umfasst: Beginnen mit einem k + 1 Bit der komprimierten differentiellen Punktiermaske (510); Erzeugen der entkomprimierten differentiellen Punktiermaske (520) durch serielles Schreiben einer Anzahl von Nullen entsprechend einem Wert, der durch nächste L Bits der komprimierten differentiellen Punktiermaske (510) angegeben ist; und Schreiben einer Eins in die entkomprimierte differentielle Punktiermaske (520).
Verfahren nach Anspruch 14, wobei die Lauflängendecodierung ferner umfasst: Wiederholen des Beginnens, Erzeugens und Schreibens beginnend mit einem k + 1 + nL Bit der komprimierten differentiellen Punktiermaske (510), wobei n jedes Mal um Eins inkrementiert wird, bis ein Ende der komprimierten differentiellen Punktiermaske (510) erreicht ist.
Verfahren nach Anspruch 15, welches ferner umfasst: nach dem Speichern des Produktes als das i Bit der Punktiermaske, Verwenden der Punktiermaske zum Löschen von Chips aus einer Datensequenz, wobei die Tatsache, dass ein Bit in der Punktiermaske eine erste Polarität aufweist, zum Ergebnis hat, dass ein erstes entsprechendes Bit in der Datensequenz gelöscht wird, und die Tatsache, dass ein Bit in der Punktiermaske eine zweite Polarität aufweist, zum Ergebnis hat, dass ein zweites entsprechendes Bit in der Datensequenz nicht gelöscht wird.
Verfahren nach Anspruch 15, welches ferner umfasst: nach dem Speichern des Produktes als das i Bit der Punktiermaske, Bit um Bit-Lesen einer Datensequenz; Bit um Bit-Lesen der Punktiermaske gleichzeitig dem mit Bit um Bit-Lesen der Datensequenz; Einfügen einer Löschung nach dem vorausgehend gelesenen Datensequenzbit, falls das entsprechende Punktiermaskenbit eine erste Polarität aufweist, und kein Einfügen einer Löschung nach dem vorausgehend gelesenen Datensequenzbit, falls das entsprechende Punktiermaskenbit eine zweite Polarität aufweist.
Vorrichtung zum Komprimieren von Punktiermaskeninformationen zur Verwendung in einem drahtlosen Kommunikationssystem, dadurch gekennzeichnet, dass die Vorrichtung aufweist: Einrichtungen zum Erstellen einer verzögerten Punktiermaske (340) mittels Löschen von letzten k Bits (320) einer Punktiermaske (310) und Anhängen von k Nullen (330) an einen Beginn der Punktiermaske (310), wobei k eine ganze Zahl ist, die größer als Eins und kleiner als n ist, wobei n eine Länge der Punktiermaske ist (310); Einrichtungen zum Erstellen einer differentiellen Punktiermaske (350) mittels XOR-Verarbeitung der verzögerten Punktiermaske (340) mit der Punktiermaske (310); und Einrichtungen zum Komprimieren der differentiellen Punktiermaske (350).
Vorrichtung nach Anspruch 18, welche ferner aufweist: Einrichtungen zum Speichern der differentiellen Punktiermaske (350) in einem Halbleiterspeicher.
Vorrichtung nach Anspruch 18, wobei die Einrichtungen zum Komprimieren der differentiellen Punktiermaske (350) dazu konfiguriert sind, die folgenden Schritte durchzuführen: Beginnen mit einem k + 1 Bit der differentiellen Punktiermaske (350), Zählen einer Anzahl von Nullen, bis eine Eins erreicht ist; und Speichern der Anzahl von Nullen im Speicher.
Vorrichtung nach Anspruch 18, wobei die Länge der Punktiermaske mindestens 1000 Bits beträgt.
Vorrichtung nach Anspruch 18, wobei die Länge der Punktiermaske mindestens 2000 Bits beträgt.
Vorrichtung nach Anspruch 18, wobei die Einrichtungen zum Komprimieren der differentiellen Punktiermaske (350) dazu konfiguriert sind, Punktiermasken aus mindestens zwei Kommunikationsstandards zu komprimieren.
Vorrichtung nach Anspruch 18, wobei die Einrichtungen zum Komprimieren der differentiellen Punktiermaske (350) dazu konfiguriert sind, mindestens 30 Punktiermasken zu komprimieren.
Vorrichtung zum Entkomprimieren und Verwenden einer Punktiermaske zur Verwendung in einem drahtlosen Kommunikationssystem, dadurch gekennzeichnet, dass die Vorrichtung aufweist: Einrichtungen zum Vorsehen einer komprimierten differentiellen Punktiermaske (510); Einrichtungen zum Entkomprimieren der komprimierten differentiellen Punktiermaske (510); Einrichtungen zum Speichern von ersten k Bits der entkomprimierten differentiellen Punktiermaske (520) als erste k Bits einer entkomprimierten Punktiermaske (530), wobei k eine ganze Zahl ist, die größer als Eins und kleiner als n ist, wobei n eine Länge der Punktiermaske ist; Einrichtungen zum Vorsehen der entkomprimierten Punktiermaske (530), die dazu konfiguriert sind, mit einem k + 1 Bit der entkomprimierten differentiellen Punktiermaske (520) zu beginnen und das k + 1 Bit der entkomprimierten differentiellen Punktiermaske (520) mit einem ersten Bit der entkomprimierten differentiellen Punktiermaske (520) mittels einer XOR-Funktion zu kombinieren, so dass sich ein Produkt ergibt; wobei die Einrichtungen zum Speichern ferner dazu konfiguriert sind, das Produkt als ein k + 1 Bit der entkomprimierten Punktiermaske (530) zu speichern; und wobei die Einrichtungen zum Entkomprimieren der komprimierten differentiellen Punktiermaske (510) ferner dazu konfiguriert sind, mit jedem Bit in der entkomprimierten differentiellen Punktiermaske (520) fortzufahren, bis ein letztes Bit erreicht ist, und jedes k + i Bit der entkomprimierten differentiellen Punktiermaske (520) mit einem i Bit der entkomprimierten Punktiermaske (530) mittels einer XOR-Funktion zu kombinieren, so dass sich ein Produkt ergibt; und wobei die Einrichtungen zum Speichern ferner dazu konfiguriert sind, das Produkt als das k + i Bit der entkomprimierten Punktiermaske (530) zu speichern.
Vorrichtung nach Anspruch 25, wobei die Länge der entkomprimierten Punktiermaske mindestens 1000 Bits beträgt.
Vorrichtung nach Anspruch 25, wobei die Länge der entkomprimierten Punktiermaske mindestens 2000 Bits beträgt.