Gerbergraph - Tanner graph

In der Codierungstheorie ist ein nach Michael Tanner benannter Tanner-Graph ein zweiteiliger Graph, der zur Angabe von Einschränkungen oder Gleichungen verwendet wird, die Fehlerkorrekturcodes angeben . In der Codierungstheorie werden Tanner-Graphen verwendet, um längere Codes aus kleineren zu konstruieren. Sowohl Encoder als auch Decoder verwenden diese Graphen ausgiebig.

Ursprünge

Tanner-Diagramme wurden von Michael Tanner vorgeschlagen, um mithilfe rekursiver Techniken aus kleineren Codes größere Fehlerkorrekturcodes zu erstellen. Er verallgemeinerte die Techniken von Elias für Produktcodes.

Tanner diskutierte Untergrenzen für die aus diesen Diagrammen erhaltenen Codes, unabhängig von den spezifischen Eigenschaften der Codes, die zur Erstellung größerer Codes verwendet wurden.

Gerbergraphen für lineare Blockcodes

Tanner Graphen sind aufgeteilt in Subcode Knoten und digit Knoten. Bei linearen Blockcodes bezeichnen die Subcodeknoten Zeilen der Paritätsprüfungsmatrix H. Die Ziffernknoten stellen die Spalten der Matrix H dar. Eine Kante verbindet einen Subcodeknoten mit einem Ziffernknoten, wenn im Schnittpunkt des entsprechenden Knotens ein Eintrag ungleich Null vorhanden ist Zeile und Spalte.

Grenzen von Tanner bewiesen

Tanner bewies die folgenden Grenzen

Sei die Rate des resultierenden linearen Codes, sei der Grad der Ziffernknoten und der Grad der Subcodeknoten . Wenn jedem Subcodeknoten ein linearer Code (n, k) mit der Rate r = k / n zugeordnet ist, ist die Rate des Codes durch begrenzt ${\ displaystyle R}$${\ displaystyle m}$${\ displaystyle n}$

${\ displaystyle R \ geq 1- (1-r) m \,}$

Rechenkomplexität von Tanner-Graph-basierten Methoden

Der Vorteil dieser rekursiven Techniken besteht darin, dass sie rechnerisch nachvollziehbar sind. Der Codierungsalgorithmus für Tanner-Graphen ist in der Praxis äußerst effizient, obwohl eine Konvergenz nicht garantiert werden kann, außer für zyklusfreie Graphen, von denen bekannt ist, dass sie keine asymptotisch guten Codes zulassen.

Anwendungen von Tanner Graph

Der Decodierungsalgorithmus von Zemor , ein rekursiver Ansatz mit geringer Komplexität für die Codekonstruktion , basiert auf Tanner-Diagrammen.

Anmerkungen

• Michael Tanners Originalpapier
• Michael Tanners Seite