Abramson/BCH-Code

16.07.2012, 11:15

Asna

Abramson/BCH-Code

Hallo, ich sitze gerade an einem Problem bei dem ich einfach nicht weiterkomme :-(
Die einzige Lösung die ich im Internet finden konnte ist leider so unhandlich, dass ich mir nicht vorstellen kann, dass es die "einzig wahre Lösung ist" Augenzwinkern

Aufgabe:
Es wird ein Kodierer benutzt, der mit g(x) einen zykl. ABRAMSON-Code erzeugt:
$\begin{eqnarray*} g(x) = m_1(x)(x+1) \end{eqnarray*}$
$\begin{eqnarray*} M(x) = x^4+x+1 primitiv \end{eqnarray*}$
Prüfen Sie folgende empfangene Binärfolgen, ob diese korrekt übertragen worden sind:
zb: $\begin{eqnarray*} b_3=(000011011001010) \end{eqnarray*}$

Die Vorgehensweise die ich im Netz finden konnte, ist:
(1) $\begin{eqnarray*} h(x)=(x^{15}-1)/g(x) \end{eqnarray*}$
(2) $\begin{eqnarray*} b_3*h(x) = 0 * mod(x^{15}-1) \end{eqnarray*}$ [fehlerfrei]
(2) $\begin{eqnarray*} b_3*h(x) \neq 0 * mod(x^{15}-1) \end{eqnarray*}$ [fehler]

Lösung:
$\begin{eqnarray*} g(x) = M(x)*(x+1)=x^5+x^4+x^2+2x+1 = (110101) \end{eqnarray*}$
$\begin{eqnarray*} h(x) = (100000000000001)/(110101) = (1110100101) restfrei \end{eqnarray*}$
$\begin{eqnarray*} b_3*h(x) = (000011011001010)* (1110100101) = 1000110110011000010 mod (100000000000001) = (110110011001010) \neq 0 \end{eqnarray*}$

16.07.2012, 12:33

Captain Kirk

Auf diesen Beitrag antworten »

Hallo,

vorab: ich kenne Abramson-Codes nicht im Speziellen, aber das von dir angesprochene Verfahren funktioniert bei allen zyklischen Codes.

(1) ist die Bestimmung des Kontrollpolynoms h. (Definiert über $\begin{eqnarray*} gh\equiv 0 \mod X^n+1 \end{eqnarray*}$ )
Wie mit Generator/Kontrollmatrizen ist ein Vektor x ein Codewort (richtig codiert) falls Hx=0 (H Kontrollmatrix), analog hier:
(2) $\begin{eqnarray*} h \cdot b_3=0 \mod X^{15}+1 \end{eqnarray*}$

Man kann das Ganze auch wieder in Matrizen übersetzen, aber in dieser Form gent's deutlich einfacher.

Zitat:

dass ich mir nicht vorstellen kann, dass es die "einzig wahre Lösung ist"

Es gibt sehr selten "einzig wahre Lösungen", sehe aber nicht wirllich vorstellen was hier so unhandlich ist. Die Multplikation der Vektoren (es ist eigentlich Polynommultiplikation) ist meines Erachtens einfacher als Matrizenmultiplikation, hier wäre g z.B. eine 15x10-Matrix. Damit zu rechnen fände ich wirklich unangenehm.

P.S. Im Körper mit zwei Elementen kann und sollte man immer + statt - schreiben.

16.07.2012, 12:42

Asna

Auf diesen Beitrag antworten »

Hallo, Danke erstmal für die Antwort!

Das ist schon mal beruhigend zu hören, dass die Vorgehensweise so passt.
[Bisher hatte die Kontrollgleichung bisher nur als Kontrollmatrix gesehen.]
[ABRAMSON ist ja im Grunde nur ein Spezialfall von BCH- bzw zyklischen Kodes.]

Das "anstrengende" hier ist wie du schon vermutet hast:

Matrixmultiplikation mit so vielen Stellen und die PolyDivi, wobei ich die noch i.O. finde.
Gibt es einen Trick für die Matrixmultipl. im Körper GF2 den Taschenrechner (nichtprogrammierbar) zu Hilfe zu nehmen?

Bei 10100000000000000000011 * 1110110001 kommt halt dann eine gekürzte Variante ala $\begin{eqnarray*} 1022041001131*10^{14} \end{eqnarray*}$ raus, also kann man hierraus nur wenige Stellen lesen.

16.07.2012, 13:29

Captain Kirk

Auf diesen Beitrag antworten »

Zitat:

10100000000000000000011 * 1110110001 kommt halt dann eine gekürzte Variante ala $\begin{eqnarray*} 1022041001131*10^{14} \end{eqnarray*}$

-Keine Ahnung was du da eingetippt hast. Zehnerpotenzen haben hier aber gar nichts zu suchen.
-Der erste Vektor ist deutlich zu lang, da $\begin{eqnarray*} X^{n+15}=X^n \mod X^{15}+1 \end{eqnarray*}$ kann man jeden Vektor auf höchsten eine Länge von 15 kürzen.

Solange eine der beiden zu multiplizierenden Zahlen weniger als 10 Einser hat kann man einen normalen Taschenrechner der im standardmäßigen dekadischen System arbeitet missbrauchen:
Bsp. 101*111=11211
Unser Ergebnis (jede Ziffer mod 2): 11011

Warum geht das? Betrachte die 10 als X: 101=1*10²+1=X²+1
Wenn aber beide zu multiplizierende Zahlen mehr als 10 Ziffern hat kann es bei der Mult. vorkommen, dass ein Koeffizient 10 oder größer wird, was im dekadischen System zu Übertragen führt, nicht aber bei der Polynommult.
Ansonsten bleibt nur die aus der Grundschule bekannte schriftliche Multiplikation, nur in diesem fall deutlich einfacher.

16.07.2012, 13:48

Asna

Auf diesen Beitrag antworten »

Also im normalen COMP Modus erhalte ich diese gekürzte Variante:

$\begin{eqnarray*} 11011001010*1110100101 = 1.222331333*10^{19} = 12223313.33*10^{12} = 1000111111*10^{10} \end{eqnarray*}$
aber genauer bekomm ich das aus dem Rechner nicht heraus =(

Ich habe gerade noch einen BINÄREN Modus gefunden:
SETUP -> BASE_N -> grüne BIN Taste
Jedoch kann ich da nur Multiplikationen bis 1111111 x 111111 [7x6 Stelllen] rechnen.

*EDIT* Und ich sehe gerade, der rechnet was ganz anderes Augenzwinkern

-> Also wäre ich einfach nur happy wenn mir mein TR bei 11011001010*1110100101 sowas wie 12223313332003441044 oder ähnlich herausbringt, damit ich 2, 3, 4 mit 0, 1, 0 ersetzen kann.

16.07.2012, 14:13

Captain Kirk

Auf diesen Beitrag antworten »

Bei weiterer Handhabung von TR steige ich aus (ich hab selber nur einen fast 20 Jahre alten)

Im Zweifelsfall: Schriftliches Multiplizieren.

16.07.2012, 14:40

Asna

Auf diesen Beitrag antworten »

Danke, nachdem ich das ganze noch 3x durchgerechnet habe, habe ich den Fehler gefunden, hatte bei h(x) eine 0 mit 1 vertauscht :-( Ich freu mich scho auf die Klausur ;D

Danke Kirk für die Hilfe !!

*closed*

Neue Frage »

Antworten »

Abramson/BCH-Code

Verwandte Themen