2025-11-20T14:55:15.130233

On the Weight Spectrum of Rate-Compatible Polar Codes

Ye, Li, Liu et al.
The weight spectrum plays a crucial role in the performance of error-correcting codes. Despite substantial theoretical exploration of polar codes with mother code length, a framework for the weight spectrum of rate-compatible polar codes remains elusive. In this paper, we address this gap by presenting the theoretical results for enumerating the number of minimum-weight codewords for quasi-uniform punctured, Wang-Liu shortened, and bit-reversal shortened decreasing polar codes. Additionally, we propose efficient algorithms for computing the average spectrum of random upper-triangular pre-transformed shortened and punctured polar codes. Notably, our algorithms operate with polynomial complexity relative to the code length. Simulation results affirm that our findings yield a precise estimation of the performance of rate-compatible polar codes.
academic

Über das Gewichtsspektrum von ratenkompatiblen Polarcodes

Grundinformationen

  • Paper-ID: 2410.19242
  • Titel: On the Weight Spectrum of Rate-Compatible Polar Codes
  • Autoren: Zicheng Ye, Yuan Li, Zhichao Liu, Huazi Zhang, Jun Wang, Guiying Yan, Zhiming Ma
  • Klassifizierung: cs.IT math.IT
  • Veröffentlichungsdatum: Oktober 2024
  • Paper-Link: https://arxiv.org/abs/2410.19242

Zusammenfassung

Das Gewichtsspektrum spielt eine entscheidende Rolle bei der Leistung von Fehlerkorrekturcodes. Obwohl umfangreiche theoretische Untersuchungen zum Gewichtsspektrum von Polarcodes mit Muttercodeländen durchgeführt wurden, bleibt das Gewichtsspektrumgerüst für ratenkompatible Polarcodes schwer fassbar. Dieser Artikel schließt diese Lücke durch die Präsentation theoretischer Ergebnisse zur Aufzählung der Anzahl von Codewörtern mit minimalem Gewicht für quasi-gleichmäßig gelöschte, Wang-Liu-verkürzte und bitinvertierte verkürzte abnehmende Polarcodes. Darüber hinaus präsentieren wir einen effizienten Algorithmus zur Berechnung des durchschnittlichen Spektrums von zufällig oberen Dreiecks-Vortransformations-verkürzten und gelöschten Polarcodes. Bemerkenswert ist, dass unsere Algorithmen eine polynomiale Komplexität bezüglich der Codelänge aufweisen. Simulationsergebnisse bestätigen, dass unsere Erkenntnisse genaue Schätzungen der Leistung ratenkompatible Polarcodes liefern.

Forschungshintergrund und Motivation

Problemhintergrund

  1. Einschränkungen von Polarcodes: Polarcodes unterliegen aufgrund der inhärenten Struktur ihres Kronecker-Produkts der Beschränkung, dass die ursprüngliche Codelänge eine Potenz von 2 sein muss. Praktische Anwendungen erfordern jedoch häufig die Übertragung von Nachrichten unterschiedlicher Codelängen, was Lösch- (Puncturing) und Verkürzungstechniken (Shortening) erfordert, um die notwendige Codelängenflexibilität bereitzustellen.
  2. Bedeutung des Gewichtsspektrums: Das Gewichtsspektrum hat erhebliche Auswirkungen auf die Leistung der Maximum-Likelihood-(ML-)Decodierung und kann durch Vereinigungsgrenzen auf der Grundlage der Anzahl von Codewörtern mit niedrigem Gewicht angenähert werden. Die Berechnung des exakten Gewichtsspektrums weist jedoch typischerweise eine exponentielle Komplexität in Bezug auf die Codelänge auf.
  3. Unzulänglichkeiten bestehender Forschung: Obwohl umfangreiche Forschungen zum Gewichtsspektrum von Polarcodes mit Muttercodeländen vorliegen, fehlt ein systematisches Gerüst für das Gewichtsspektrum ratenkompatible Polarcodes. Bestehende Methoden weisen entweder zu hohe Komplexität auf oder haben begrenzte Anwendbarkeit.

Forschungsmotivation

Dieser Artikel zielt darauf ab, die Lücke in der Theorie des Gewichtsspektrums ratenkompatible Polarcodes zu schließen und ein systematisches Gewichtsspektrum-Analysegerüst für quasi-gleichmäßig gelöschte (QUP), Wang-Liu-verkürzte und bitinvertierte verkürzte Polarcodes bereitzustellen.

Kernbeiträge

  1. Theoretische Beiträge: Präsentation eines vollständigen theoretischen Gerüsts und von Formeln zur Berechnung der Anzahl von Codewörtern mit minimalem Gewicht für QUP-, Wang-Liu-verkürzte und bitinvertierte verkürzte abnehmende Polarcodes.
  2. Algorithmische Innovation: Entwicklung von Algorithmen mit polynomialer Komplexität zur Berechnung des durchschnittlichen Gewichtsspektrums von zufällig oberen Dreiecks-Vortransformations-verkürzten und gelöschten Polarcodes.
  3. Leistungsbewertung: Verifikation durch Simulation, dass die vorgeschlagenen Methoden die Leistung ratenkompatible Polarcodes genau schätzen können, besonders unter Hochsignal-Rausch-Verhältnis-Bedingungen.
  4. Komplexitätsoptimierung: Alle vorgeschlagenen Algorithmen weisen eine polynomiale Komplexität bezüglich der Codelänge auf und gewährleisten damit Skalierbarkeit und praktische Anwendbarkeit der Methoden.

Methodische Erläuterung

Aufgabendefinition

Die Kernaufgabe dieser Forschung ist die Berechnung des Gewichtsspektrums ratenkompatible Polarcodes, insbesondere die Anzahl von Codewörtern mit minimalem Gewicht. Gegeben eine Informationsmenge I und ein Ratenanpassungsmuster (Lösch- oder Verkürzungsmuster) besteht das Ziel darin, die Verteilung des Codewortgewichts zu bestimmen.

Theoretische Grundlagen

Monomiale Darstellung von Polarcodes

Polarcodes können als monomiale Codes im Ring F₂x₁,...,xₘ/(x₁²-x₁,...,xₘ²-xₘ) beschrieben werden. Die monomiale Menge ist definiert als:

M ≜ {x₁^(a₁)...xₘ^(aₘ) | (a₁,...,aₘ) ∈ F₂ᵐ}

Abnehmende monomiale Codes

Eine Informationsmenge I⊆M ist abnehmend, wenn ∀f≼g und g∈I, dann f∈I. Hier bezeichnet ≼ die Teilordnungsrelation von Monomialen.

Kernalgorithmen

1. Bitinvertierte verkürzte Polarcodes

Theorem 2: Sei C(I,Y'ᵢ) ein verkürzter abnehmender r-ter Ordnung Polarcode der Länge N=2ᵐ mit Verkürzungsmuster Y'ᵢ. Für ein Monom f vom Grad r ist die Anzahl der Codewörter mit minimalem Gewicht d=2^(m-r):

|Tf(d,Y'ᵢ)| = λf(1 - βf(i)/2ʳ)

wobei βf(i) die Anzahl der Faktoren von f in Y'ᵢ ist.

Algorithmus 1 beschreibt den Berechnungsprozess:

  • Komplexität: O(|Y'||Iᵣ|) = O(N²)
  • Berechnung der Anzahl verkürzter Faktoren für jedes Monom f vom Grad r
  • Rekursive Aktualisierung der verbleibenden Codewortanzahl

2. QUP-Polarcodes

Durch Lemma 5 werden iterative Gleichungen zur Berechnung von Pf(d,a) etabliert:

Für ein Monom f = xᵢ₁...xᵢₜ, definiere Nf(w,a) als die Anzahl der Codewörter mit Gewicht w in den ersten a Bits, dann:

  • Wenn a ≤ 2^(it-1), w≠0: Nf(w,a) = Σₛ∈B(f,t) 2^αf(s)Nf(s)(w,a) + Nf(0)(w,a)
  • Wenn 2^(it-1) < a ≤ 2^it: Nf(w,a) = Nf(2^(it-t) - w, 2^it - a)
  • Wenn a > 2^it: Nf(w,a) = Nf(w - 2^(it-t), a - 2^it)

3. Durchschnittliches Gewichtsspektrum vortransformierter Polarcodes

Theorem 7 gibt das durchschnittliche Gewichtsspektrum vortransformierter Polarcodes an:

E[N(d,T,X)] = Σ₁≤j≤K 2^(K-j)Ad(m,(0₁^(Ij-1),1),X) / 2^(N-Ij)

Implementiert durch Algorithmus 3 mit Komplexität O(N³).

Technische Innovationspunkte

  1. Einheitliches Gerüst: Erstmalige Bereitstellung eines einheitlichen Gewichtsspektrum-Analysegerüsts für mehrere Ratenanpassungsmuster.
  2. Polynomiale Komplexität: Alle Algorithmen erreichen polynomiale Komplexität und durchbrechen damit die Beschränkung der traditionellen exponentiellen Komplexität.
  3. Nutzung von Symmetrie: Geschickte Nutzung der Symmetrieeigenschaften von Codewörtern zur Vereinfachung der Berechnung, wie z.B. Wang-Liu-Verkürzung kann durch die Symmetrie von QUP erhalten werden.
  4. Rekursive Zerlegung: Reduktion der Rechenkomplexität durch Zerlegung eines Codes der Länge N in zwei Untercodes der Länge N/2.

Experimentelle Einrichtung

Datensätze und Parameter

  • Codelänge: N = 32, 96, 768, 896 usw.
  • Anzahl der Informationsbits: K = 24, 48, 72, 192, 384, 576 usw.
  • Informationsmengenwahl: Basierend auf der Gaußschen Approximationsmethode (GA)
  • Vortransformation: PC-Polarcodes (mit 5-Längen-Schieberegister mit linearer Rückkopplung)

Bewertungsmetriken

  • Minimales Gewicht dₘᵢₙ und Anzahl der Codewörter mit minimalem Gewicht Aₘᵢₙ
  • Vereinigungsgrenzen (Union Bound) berechnete Blockfehlerrate (BLER)
  • Tatsächliche Leistung der SCL-Decodierung (Listengröße 32)

Vergleichsmethoden

  • Durch SCL-Decodierung erfasstes Gewichtsspektrum
  • Traditionelle exakte Berechnungsmethode mit exponentieller Komplexität
  • Näherungsergebnisse probabilistischer Methoden

Experimentelle Ergebnisse

Hauptergebnisse

Tabelle 2 zeigt den Vergleich zwischen theoretischer Berechnung und durch SCL-Decodierung erfassten Ergebnissen:

  • Wenn die Anzahl der gelöschten Bits gering ist, stimmen die theoretische Untergrenze und der tatsächliche Wert vollständig überein
  • Mit zunehmender Anzahl gelöschter Bits kann die Untergrenze erheblich unter dem tatsächlichen Wert liegen, da Codewörter mit hohem Gewicht nach dem Löschen zu niedrigem Gewicht werden können

Tabelle 3 zeigt das minimale Gewicht und die Anzahl der Codewörter mit minimalem Gewicht verschiedener Codes:

  • QUP: dₘᵢₙ = 12, Aₘᵢₙ = 56 (96,24-Code)
  • Wang-Liu-Verkürzung: dₘᵢₙ = 16, Aₘᵢₙ = 292
  • Bitinvertierte Verkürzung: dₘᵢₙ = 16, Aₘᵢₙ = 490

Leistungsverifikation

Abbildungen 1-8 zeigen den Vergleich zwischen Vereinigungsgrenzen und SCL-Decodierungsleistung:

  • Bei hohem Signal-Rausch-Verhältnis stimmen die theoretischen Vereinigungsgrenzen und die tatsächliche SCL-Leistung hochgradig überein
  • Für vortransformierte Polarcodes kann das durchschnittliche Gewichtsspektrum die Leistung gleichermaßen genau vorhersagen
  • Verifikation der Genauigkeit und praktischen Anwendbarkeit der vorgeschlagenen Methoden

Komplexitätsanalyse

  • Algorithmus 1 (Bitinvertierte Verkürzung): O(N²)
  • Algorithmus 2 (QUP): O(N³)
  • Algorithmus 3 (Durchschnittliches Spektrum der Vortransformation): O(N³)

Verwandte Arbeiten

Gewichtsspektrum-Forschung zu Polarcodes

  • Bardet et al. betrachten Polarcodes als abnehmende monomiale Codes und wenden LTA-Automorphismen an, um die Anzahl der Codewörter mit minimalem Gewicht zu bestimmen
  • Nachfolgende Forschungen quantifizieren die Anzahl der Codewörter mit Gewichten unter 1,5wₘᵢₙ und 2wₘᵢₙ

Algorithmische Methoden

  • Methode zur Erfassung von Codewörtern mit niedrigem Gewicht durch SCL-Decodierung
  • Probabilistische Näherungsmethoden mit polynomialer Komplexität
  • Baumschnittmethode zur Reduktion der Rechenkomplexität

Vortransformierte Polarcodes

  • Vortransformationsmethoden wie CRC-gestützt, Paritätsprüfung, PAC-Codes usw.
  • Theoretischer Nachweis, dass obere Dreiecks-Vortransformation die Codedistanz nicht reduziert
  • Rekursive Formeln für durchschnittliche Gewichtsspektren

Schlussfolgerungen und Diskussion

Hauptschlussfolgerungen

  1. Etablierung eines vollständigen theoretischen Gerüsts für das Gewichtsspektrum ratenkompatible Polarcodes
  2. Bereitstellung effizienter Algorithmen mit polynomialer Komplexität
  3. Theoretische Vorhersagen stimmen mit tatsächlicher Leistung hochgradig überein, besonders bei hohem Signal-Rausch-Verhältnis

Einschränkungen

  1. Bei großem Umfang von Löschungen kann die Untergrenze der Anzahl von Codewörtern mit minimalem Gewicht möglicherweise nicht ausreichend eng sein
  2. Obwohl die Algorithmen-Komplexität polynomial ist, können extrem lange Codes immer noch rechnerische Herausforderungen darstellen
  3. Hauptfokus auf abnehmende Polarcodes mit begrenzter Anwendbarkeit auf nicht-abnehmende Codes

Zukünftige Richtungen

  1. Verbesserung der engen Schätzung der Gewichtsspektrum-Grenzen für gelöschte Codes
  2. Erweiterung auf allgemeinere Polarcode-Konstruktionsmethoden
  3. Untersuchung der Beziehung zwischen Gewichtsspektrum und anderen Leistungsindikatoren

Tiefgreifende Bewertung

Stärken

  1. Theoretische Vollständigkeit: Erstmalige Bereitstellung eines einheitlichen theoretischen Gerüsts für mehrere Ratenanpassungsmuster, Schließung einer wichtigen theoretischen Lücke
  2. Algorithmen-Effizienz: Die Realisierung polynomialer Komplexität ist ein großer Durchbruch, der die Gewichtsspektrum-Berechnung für lange Codes ermöglicht
  3. Experimentelle Verifikation: Umfangreiche Simulationsverifikation der Genauigkeit der Theorie, besonders die Übereinstimmung zwischen Vereinigungsgrenzen und tatsächlicher Leistung
  4. Praktischer Wert: Methoden können direkt zur Leistungsvorhersage und Optimierungsdesign von Polarcodes verwendet werden

Mängel

  1. Lockere Untergrenze: Bei hoher Löschungsrate kann die theoretische Untergrenze den tatsächlichen Wert erheblich unterschätzen
  2. Anwendungsbereich: Hauptsächlich anwendbar auf abnehmende Polarcodes, was die Universalität einschränkt
  3. Komplexität: Obwohl polynomial, stellt O(N³) für extrem lange Codes immer noch eine Herausforderung dar

Einfluss

  1. Akademischer Beitrag: Bereitstellung wichtiger Analysewerkzeuge für die Polarcode-Theorie, Förderung der theoretischen Entwicklung dieses Feldes
  2. Praktischer Wert: Theoretische Unterstützung für Design und Optimierung von Polarcodes in 5G/6G-Kommunikationssystemen
  3. Methodologie: Die Designideen für Algorithmen mit polynomialer Komplexität haben Referenzwert für andere Codierungstheorie-Probleme

Anwendungsszenarien

  1. Kommunikationssystem-Design: Szenarien wie 5G NR, Satellitenkommunikation usw., die ratenkompatible Polarcodes erfordern
  2. Leistungsanalyse: Anwendungen, die schnelle und genaue Vorhersage der Polarcode-Leistung benötigen
  3. Codewort-Optimierung: Polarcode-Konstruktion und Parameteroptimierung basierend auf Gewichtsspektrum

Literaturverzeichnis

Das Papier zitiert 40 wichtige Referenzen, die grundlegende Polarcode-Theorie, Gewichtsspektrum-Analyse, Vortransformationstechniken und Ratenanpassung abdecken und eine solide theoretische Grundlage für die Forschung bieten.