RDS CRC Prüfbit Berechnung

[Bernhard S. (bernhard)]

Geschätzes Forum,

ich habe mal RDS-Rohdaten mitgeschnitten und in der XLS-Datei etwas 
aufbereitet.

Meine Frage:

Wie kann man die Prüfbits bzw. CRC berechnen, mit der Norm EN50067 
(s.Anhang) werde ich nicht schlau.

Vielleicht könnt Ihr mir mal einfach erklären, wie die Berechnung 
erfolgt.


Die Prüfbittberechnung ist ein Teil von diesem Projekt:

Beitrag "RDS DECODER analog Schaltung ohne IC gesucht, für Rohdatengewinnung"

Danke


Bernhard

[Detlef K. (adenin)]

Vielleich hilft dir der Sourcecode von einem Softwaredecoder.
https://www.cgran.org/wiki/RDS

[Bernhard S. (bernhard)]

@alle

zu einer kleinen Erkenntnis kam ich.

Beim Gruppentyp "D" ist mir etwas aufgefallen,

wenn alle 16 Datenbits  NULL sind,

dann sind die Prüfbits (Checkword und Offset) gleich dem

Tabelleneintrag im Annex A im Page59 der EN50067.


@Detlef Kunz

ich danke Dir, hab mal geschaut, leider blieb der "Aha"-Efekt noch aus.

Bernhard

[Bernhard S. (bernhard)]

@alle

diese Threads fand ich sehr interessant:

Beitrag "Probleme mit RDS Synchronisation"

Beitrag "RDS-Empfang"

Bernhard

[Detlef K. (adenin)]

Q+D
Ich hoffe das hilft.

#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>

#define OFFSET_WORD_A 0x0FC

unsigned int calc_rds_crc (uint16_t data)
{
  int i;
  uint16_t polynom=0x05B9;
  uint16_t BitMask=0x8000;
  uint16_t crc = 0;

  for (i=16; i>0; i--)   //das ganze 16 mal (einmal für jedes Datenbit)
  {
    crc = crc << 1;      //CRC um ein Bit nach links schieben, dabei wird Bit0 mit 0 aufgefüllt

    if (data & BitMask)  //Bitmaske testet in der Schleife nacheinander alle Datenbits beginnend bei D0
      crc = crc | 1;     //ist das Datenbit 1, dann wird Bit 0 von CRC gesetzt, ansonsten bleibt es 0 

    if (crc & 0x0400)       //Bit10 dec CRC testen
      crc = crc ^ polynom;  //wenn es gesetzt ist, dann CRC mit POLYNOM XOR-Verknüpfen

    BitMask >>= 1;  //Bitmaske nach recht schieben für das nächste Bit
        }

//und noch ne Schleife
  for (i=10;i>0;i--)   //einmal für jedes Polynombit (also 10 mal)
  {
    crc = crc << 1;      //CRC ein Bit nach links

    if (crc & (1<<10))      //ist das 10. Bit gesetzt?
      crc = crc ^ polynom;  //ja, dann CRC mit POLYNOM XOR-Verknüpfen
        }

        return crc  & 0x3ff;   //die 10 Bit des CRC als Ergebnis liefern
}



int main(int argc, char *argv[])
{


  printf("test: %x\n", calc_rds_crc(0xd4f1) ^ OFFSET_WORD_A); //Das CRC mit dem OFFSET_WORD XOR-Verknüpft ergibt dein Ergebnis

  return EXIT_SUCCESS;
}

[Bernhard S. (bernhard)]

@Detlef

ich danke Dir, werde mich mit dem Code beschäftigen und einen 
Zusammenhang zur EN50067 suchen.

Bernhard

[Abdul K. (ehydra)]

Was heißt denn Q+D ?

[Rene H. (Gast)]

Abdul K. schrieb:
> Was heißt denn Q+D ?

Quick and dirty

[Bernhard S. (bernhard)]

@Detlef
@alle

wenn ich es richtig deute, dann befindet sich die 2.Schleife in der 
1.Schleife.

D.h. bei jedem Schleifendurchlauf der 1.Schleife, wird 10 mal die 
2.Schleife durchlaufen?

Mich wundert das gemeinsame "i", beienflussen sich die beiden "i" nicht 
gegenseitig?

Bernhard

[Detlef K. (adenin)]

Nein, das sind zwei seperate Schleifen.
Nur die Klammern sind beim CopyPaste aus irgendeinen Grund verschoben.
Die ganze Einrückung des Textes sieht etwas merkwürdig aus. :(

[Detlef K. (adenin)]

So, sieht netwas besser aus.

#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>

#define OFFSET_WORD_A 0x0FC

unsigned int calc_rds_crc (uint16_t data)
{
  int i;
  uint16_t polynom=0x05B9;
  uint16_t BitMask=0x8000;
  uint16_t crc = 0;

//-erste Schleife--------------------------
  for (i=16; i>0; i--)   //das ganze 16 mal (einmal für jedes Datenbit)
  {
    crc = crc << 1;      //CRC um ein Bit nach links schieben, dabei wird Bit0 mit 0 aufgefüllt

    if (data & BitMask)  //Bitmaske testet in der Schleife nacheinander alle Datenbits beginnend bei D0
      crc = crc | 1;     //ist das Datenbit 1, dann wird Bit 0 von CRC gesetzt, ansonsten bleibt es 0 

    if (crc & 0x0400)       //Bit10 dec CRC testen
      crc = crc ^ polynom;  //wenn es gesetzt ist, dann CRC mit POLYNOM XOR-Verknüpfen

    BitMask >>= 1;  //Bitmaske nach recht schieben für das nächste Bit
  }

//-zweite Schleife--------------------------
  for (i=10;i>0;i--)   //einmal für jedes Polynombit (also 10 mal)
  {
    crc = crc << 1;      //CRC ein Bit nach links

    if (crc & (1<<10))      //ist das 10. Bit gesetzt?
      crc = crc ^ polynom;  //ja, dann CRC mit POLYNOM XOR-Verknüpfen
  }

  return crc  & 0x3ff;   //die 10 Bit des CRC als Ergebnis liefern
}



int main(int argc, char *argv[])
{


  printf("test: %x\n", calc_rds_crc(0xd4f1) ^ OFFSET_WORD_A); //Das CRC mit dem OFFSET_WORD XOR-Verknüpft ergibt dein Ergebnis

  return EXIT_SUCCESS;
}

[Bernhard S. (bernhard)]

Danke für die schnelle Antwort, ich versuch's gerade im Excel 
nachzuvollziehen.

Bernhard

[Detlef K. (adenin)]

noch ein etwas optimiert

unsigned int calc_rds_crc (uint16_t data)
{
  int i;
  uint16_t polynom=0x05B9;
  uint16_t BitMask=0x8000;
  uint16_t crc = 0;

  uint16_t tmp = data;
  for (i=26; i>0; i--)                       //das ganze 16 mal (einmal für jedes Datenbit) PLUS 10 mal mit 0-Bits
  {
    crc = crc << 1 | ((tmp & 0x8000)>>15);   //CRC um ein Bit nach links schieben, dabei wird Bit0 mit einem Datenbit ausgefüllt

    if (crc & 0x0400)                        //Bit10 des CRC testen
      crc = crc ^ polynom;                   //wenn es gesetzt ist, dann CRC mit POLYNOM XOR-Verknüpfen

    tmp <<= 1;                               //nächstes Datenbit in Position bringen
  }

  return crc  & 0x3ff;                       //die 10 Bit des CRC als Ergebnis liefern
}

[Detlef K. (adenin)]

Bernhard S. schrieb:
> Danke für die schnelle Antwort, ich versuch's gerade im Excel
> nachzuvollziehen.
>
> Bernhard

Vergiß nicht die Xor-Verknüpfung des Ergebnis mit dem Offset_Word zum 
Schluß!

[Bernhard S. (bernhard)]

Das müsste die erste Schleife sein, wenn ich es richtig gedeutet habe.

Ich hoffe es hat sich kein Fehler eingschlichen, denn bis jetzt habe ich 
keine Kontrollmöglichkeit.

Detlef, könntest Du mir mal die Zwischenergebnisse der Schleife 1 und 2 
zur Verfügung stellen, wenn Data x8000 also 0b1000000000000000 ist?


Die Daten und CRC stammen von einem RDS Mittschnitt, müsste fehlerfrei 
sein.


>Vergiß nicht die Xor-Verknüpfung des Ergebnis mit dem Offset_Word zum
>Schluß!

ok, ich denke dran ;-)

Bernhard

[Detlef K. (adenin)]

für 0x8000
erste Schleife 0x2C7
zweite Schleife 0x77

[Bernhard S. (bernhard)]

DANKE !

[Detlef K. (adenin)]

Die Zwischenergebnisse (in hex) der ersten Schleife für jeden Durchgang

1 crc: 1
2 crc: 2
3 crc: 4
4 crc: 8
5 crc: 10
6 crc: 20
7 crc: 40
8 crc: 80
9 crc: 100
10 crc: 200
11 crc: 1b9
12 crc: 372
13 crc: 35d
14 crc: 303
15 crc: 3bf
16 crc: 2c7

[Bernhard S. (bernhard)]

Sehr gut, hab irgendwo noch einen Fehler, damit müsste ich ihn schnell 
finden :-)

[Bernhard S. (bernhard)]

Seltsam, bis x200 stimmts und dann Fehler, als würde mit der 
xor-Verknüpfung des Polynoms x06B9 etwas nicht stimmen ?

[Detlef K. (adenin)]

0x5b9 ;)

Wie ist dein Zwischenergebnis?
edit:
Ahja, ich hab eben die excel-Datei entdeckt.

[Detlef K. (adenin)]

Hm, dein XOR ist falsch

Richtig:
a b | y
----+--
0 0 | 0
0 1 | 1
1 0 | 1
1 1 | 0

Du benutzt aber XNOR
a b | y
----+--
0 0 | 1
0 1 | 0
1 0 | 0
1 1 | 1

[Bernhard S. (bernhard)]

>Du benutzt aber XNOR

Du hast Recht, hab's geändert.

Hab noch einen 2 Fehler in der Excel-Tabelle:

Bit 10 muss auf "1" getestet werden ich teste Bit 9.

[Bernhard S. (bernhard)]

@alle

Ein kleines Beispiel, wie die Prüfbits berechnet werden können,

Detlef, ich danke Dir für die sehr wertvolle Unterstützung !

Bernhard

[Bernhard S. (bernhard)]

@alle

ein kleiner RDS CRC Prüfbit Rechner Calculator in Excel.

Die 16-Bit Daten können hexadzimal eingegeben werden z.B. D4F1.

Im Ergebnis der Berechnung werden die Prüfsummen für alle Gruppentypen / 
RDS Gruppen ausgegeben.

@Detlef

könntest Du mir mal bitte diesen Rechner für x01 bis x20 testen. Habe 
jetzt tagelang RDS-Daten mitgeschnitten, aber solche Datenbits wurden 
nicht gesendet.

Bernhard

[Detlef K. (adenin)]

Sowas?

Data: 0x0001     crc: 0x1b9      A: 0x145        C: 0x021        B: 0x0d1        D: 0x00d
Data: 0x0002     crc: 0x372      A: 0x38e        C: 0x2ea        B: 0x21a        D: 0x2c6
Data: 0x0003     crc: 0x2cb      A: 0x237        C: 0x353        B: 0x3a3        D: 0x37f
Data: 0x0004     crc: 0x35d      A: 0x3a1        C: 0x2c5        B: 0x235        D: 0x2e9
Data: 0x0005     crc: 0x2e4      A: 0x218        C: 0x37c        B: 0x38c        D: 0x350
Data: 0x0006     crc: 0x02f      A: 0x0d3        C: 0x1b7        B: 0x147        D: 0x19b
Data: 0x0007     crc: 0x196      A: 0x16a        C: 0x00e        B: 0x0fe        D: 0x022
Data: 0x0008     crc: 0x303      A: 0x3ff        C: 0x29b        B: 0x26b        D: 0x2b7
Data: 0x0009     crc: 0x2ba      A: 0x246        C: 0x322        B: 0x3d2        D: 0x30e
Data: 0x000a     crc: 0x071      A: 0x08d        C: 0x1e9        B: 0x119        D: 0x1c5
Data: 0x000b     crc: 0x1c8      A: 0x134        C: 0x050        B: 0x0a0        D: 0x07c
Data: 0x000c     crc: 0x05e      A: 0x0a2        C: 0x1c6        B: 0x136        D: 0x1ea
Data: 0x000d     crc: 0x1e7      A: 0x11b        C: 0x07f        B: 0x08f        D: 0x053
Data: 0x000e     crc: 0x32c      A: 0x3d0        C: 0x2b4        B: 0x244        D: 0x298
Data: 0x000f     crc: 0x295      A: 0x269        C: 0x30d        B: 0x3fd        D: 0x321
Data: 0x0010     crc: 0x3bf      A: 0x343        C: 0x227        B: 0x2d7        D: 0x20b
Data: 0x0011     crc: 0x206      A: 0x2fa        C: 0x39e        B: 0x36e        D: 0x3b2
Data: 0x0012     crc: 0x0cd      A: 0x031        C: 0x155        B: 0x1a5        D: 0x179
Data: 0x0013     crc: 0x174      A: 0x188        C: 0x0ec        B: 0x01c        D: 0x0c0
Data: 0x0014     crc: 0x0e2      A: 0x01e        C: 0x17a        B: 0x18a        D: 0x156
Data: 0x0015     crc: 0x15b      A: 0x1a7        C: 0x0c3        B: 0x033        D: 0x0ef
Data: 0x0016     crc: 0x390      A: 0x36c        C: 0x208        B: 0x2f8        D: 0x224
Data: 0x0017     crc: 0x229      A: 0x2d5        C: 0x3b1        B: 0x341        D: 0x39d
Data: 0x0018     crc: 0x0bc      A: 0x040        C: 0x124        B: 0x1d4        D: 0x108
Data: 0x0019     crc: 0x105      A: 0x1f9        C: 0x09d        B: 0x06d        D: 0x0b1
Data: 0x001a     crc: 0x3ce      A: 0x332        C: 0x256        B: 0x2a6        D: 0x27a
Data: 0x001b     crc: 0x277      A: 0x28b        C: 0x3ef        B: 0x31f        D: 0x3c3
Data: 0x001c     crc: 0x3e1      A: 0x31d        C: 0x279        B: 0x289        D: 0x255
Data: 0x001d     crc: 0x258      A: 0x2a4        C: 0x3c0        B: 0x330        D: 0x3ec
Data: 0x001e     crc: 0x093      A: 0x06f        C: 0x10b        B: 0x1fb        D: 0x127
Data: 0x001f     crc: 0x12a      A: 0x1d6        C: 0x0b2        B: 0x042        D: 0x09e
Data: 0x0020     crc: 0x2c7      A: 0x23b        C: 0x35f        B: 0x3af        D: 0x373

[Bernhard S. (bernhard)]

Ja, ich bin begeistert :-)

Der Prüfbit Calculator funktioniert fehlerfrei

Danke

Noch eine Frage, hast Du Dich schon mit dem Matrixverfahren beschäftigt?

Bernhard

[Detlef K. (adenin)]

Nö.
Du willst die Fehlerkorrektur in Excel machen?

[Bernhard S. (bernhard)]

>Du willst die Fehlerkorrektur in Excel machen?

Ich dachte die H-Matrix dient auch zur Prüfbitermittlung?

Probieren würde ich es gern in Excel, bevor ich mich an die 
Assembler-Programmierung wage.

Bernhard

[Bernhard S. (bernhard)]

@alle

Eine VBA Visual Basic Variante.

Ein Datenstring von 26 Bites wird an die Funktion übergeben als Antwort 
erhält man eine 0 für Error (z.B. CRC Error), 1 für Gruppe-A, 2 für 
Gruppe-B, 3 für Gruppe-C, 4 für die Gruppe-D.



Public Function BERECHNUNG_CRC(INP As String) As Byte
' INPUT: STRING 26 BYTES
' z.B.  ("10000000000000000111000011")
'       ("11010100111100011010001111")
' OUT:
'   0= Error
'   1=Gruppe A
'   2=Gruppe B
'   3=Gruppe C
'   4=Gruppe D
Dim i As Integer
Dim ZWISCHENERGEBNIS1
Dim ZWISCHENERGEBNIS2
Dim DATA As Double
Dim CRC_OLD As Double
Dim CRC As Double
Dim CRC_GRUPPE_A
Dim CRC_GRUPPE_B
Dim CRC_GRUPPE_C
Dim CRC_GRUPPE_D
'----------------------------------------------------------------------- 
------------------
' Länge-Check
If Len(INP) <> 26 Then Exit Function
' DATA UMWANDELN
For i = 0 To 15
    DATA = DATA + Mid(INP, 16 - i, 1) * 2 ^ i
Next i
' CRC-OLD UMWANDELN
For i = 0 To 9
    CRC_OLD = CRC_OLD + Mid(INP, 26 - i, 1) * 2 ^ i
Next i
'----------------------------------------------------------------------- 
------------------
' 1. Schleife 16xDatenbits behandeln
For i = 0 To 15
    DATA = DATA * 2             ' DATA 1 x links
        If DATA > &HFFFF& Then  ' mehr als 16 Bits ?
            CRC = CRC * 2 + 1   '  1 x links und 1 reinschieben
        Else
            CRC = CRC * 2       '  1 x links und 0 reinschieben
        End If
    If CRC > &H3FF& Then
        CRC = CRC Xor &H5B9&    ' XOR Polynom 0x5B9
    End If
    DATA = DATA And &HFFFF&     ' größer 16 BIT abschneiden
Next i
    ZWISCHENERGEBNIS1 = Hex(CRC)
'----------------------------------------------------------------------- 
------------------
' 2. Schleife 10xCRC-Bits behandeln
For i = 0 To 9
    CRC = CRC * 2               ' CRC 1 x links
    If CRC > &H3FF& Then        ' mehr als 10 Bits ?
        CRC = CRC Xor &H5B9&    ' XOR Polynom 0x5B9
    End If
    CRC = CRC And &H3FF&        ' größer 10 BIT abschneiden
Next i
    ZWISCHENERGEBNIS2 = Hex(CRC)
'----------------------------------------------------------------------- 
------------------
' MASTER-WORD
CRC_GRUPPE_A = CRC Xor &HFC&
CRC_GRUPPE_B = CRC Xor &H198&
CRC_GRUPPE_C = CRC Xor &H168&
CRC_GRUPPE_D = CRC Xor &H1B4&
'----------------------------------------------------------------------- 
------------------
' CRC vergleich CRC mit CRC_OLD
BERECHNUNG_CRC = 0
If CRC_GRUPPE_A = CRC_OLD Then BERECHNUNG_CRC = 1
If CRC_GRUPPE_B = CRC_OLD Then BERECHNUNG_CRC = 2
If CRC_GRUPPE_C = CRC_OLD Then BERECHNUNG_CRC = 3
If CRC_GRUPPE_D = CRC_OLD Then BERECHNUNG_CRC = 4
End Function

[Detlef K. (adenin)]

Assembler? Welche CPU?
Ich schau mir mal die Fehlerkorrektur an, kann aber nichts versprechen. 
;)

[Bernhard S. (bernhard)]

ATmega8

[Detlef K. (adenin)]

// Q+D
// nur mal schnell als Beispiel zum testen


.include "m8def.inc"

.equ  POLYNOM    = 0x5B9
.equ  OFFSET_WORD_A  = 0x0FC
.equ  OFFSET_WORD_B  = 0x198
.equ  OFFSET_WORD_C  = 0x168
.equ  OFFSET_WORD_D  = 0x1B4



  .cseg
  .org 0
  rjmp  _Reset

_Reset:
  ldi  r16,low(RAMEND)
  out  spl,r16
  ldi  r16,high(RAMEND)
  out  sph,r16


  ldi  r16,low(0xd4f1)
  sts  data,r16
  ldi  r16,high(0xd4f1)
  sts  data+1,r16

Main:
  rcall  rds_crc
  rjmp  Main



rds_crc:
  push  r3
  push  r4
  push  r16
  push  r17
  push  r18


//temporäres CRC (r3,r4) auf 0 setzen    
  clr  r3
  clr  r4

// erste Teilaufgabe
  ldi  r18,8
  lds  r16,data+1  //die ersten 8 Datenbit
  rcall  crc_loop

// zweite Teilaufgabe
  ldi  r18,8
  lds  r16,data  //die restlichen 8 Datenbit verarbeiten
  rcall  crc_loop

//dritte Teilaufgabe
  ldi  r18,10    //10 0-Bits verarbeiten
  clr  r16    //dummy
  rcall  crc_loop


// mit OFFSET_WORD_A verknüpfen
  ldi  r17,low(OFFSET_WORD_A)
  eor  r3,r17
  ldi  r17,high(OFFSET_WORD_A)
  eor  r4,r17

// CRC abspeichern
  sts  crc,r3
  sts  crc+1,r4


  pop  r18
  pop  r17
  pop  r16
  pop  r4
  pop  r3
  ret


crc_loop:
_loop:
  lsl  r16
  rol  r3
  rol  r4
  sbrs  r4,2
  rjmp  _kein_xor
  ldi  r17,low(POLYNOM)
  eor  r3,r17
  ldi  r17,high(POLYNOM)
  eor  r4,r17
_kein_xor:
  dec  r18
  brne  _loop
  ret

  .dseg
data:  .BYTE  2
crc:  .BYTE  2

[Bernhard S. (bernhard)]

Danke Detlef, das ist schon mal eine sehr wertvolle Grundlage :-)

Gruß

Bernhard

[adenin (Gast)]

Naja, es ist nur die Umsetztung dieser CRC-Routine in AVR.
Das Problem: Die Sache der Decodierung ist viel komplexer.
Du solltes doch nochmal in den Source schauen, was dazu alles nötig ist:
https://www.cgran.org/wiki/RDS

[Bernhard S. (bernhard)]

>Das Problem: Die Sache der Decodierung ist viel komplexer.

Die einzelnen Gruppen und Blöcke kann ich in Assembler und VBA schon 
ganz brauchbar zusammenfügen. Bei vernünftigem RDS-Empfang wird der 
Datenstrom nach spätestens 107 Byte synchronisiert

Hab mich mal mit der Fehlerkorrektur beschäftigt und folgendes Programm 
geschrieben:

Wenn die CRC-Bits einer Gruppe nicht zu den beiden DATEN-Bits passen, 
dann wird nacheinander jedes einzelne Daten und CRC-Bit (26Bit) 
invertiert und der CRC-Check durchgeführt.

Die Gruppen-Errors nahmen sofort ab, aber es entstanden plötzlich auch 
falsche Grubben und sogar falsche Blöcke.

Bin noch am überlegen, ob sich die Fehlerkorrektur wirklich lohnt, keine 
Daten können besser sein als falsche.

[Bernhard S. (bernhard)]

@alle

so könnte es in einem fertigen Projekt verwirklicht werden:

Beitrag "RDS DECODER LCD TWI 2WIRE USART ATmega8 Assembler"


@Detlef

ich danke Dir nochmals für die sehr hilfreiche Unterstützung :-)

Bernhard

[Bernhard S. (bernhard)]

@alle

hiermit könnte man RDS-Gruppen senden, ein kleiner RDS-Generator:

Beitrag "RDS ENCODER Signalgenerator Testgenerator Testsender Modulator ATmega8 Assembler"


Bernhard