RDS matematika

[msar]

Věděl by prosím někdo jak se vypočítá kontrolní 10bit slovo z přijatého 16bit slova? Nějak to nemůžu pochopit. Přikládám vyňatek z EN50067 Rds Standard

[Hill]

Něco o tom jsem kdysi našel tady : http://www.pira.cz/navody.htm#teorie , pravděpodobně na těch stránkách najdeš i kontakt na lidi, co se tím zabývají.
Jinak musíš tu normu seštudovat celou včetně příloh, ty jsou snad ještě důležitější, než samotná norma.

[Piitr]

Musíš s tím počítat jako s polynomem.
Třeba 10 bitů dat 1101101100 musíš chápat jako polynom:
1*x^9 + 1*x^8 + 0*x^7 + 1*x^6 + ... + 0*x^1 + 0*x^0

Další věc je, že počítáš modulo 2:
0+0=0
0+1=1+0=1
1+1=0
Takže sčítání odpovídá operaci exlusive or (XOR).

Takže:
Data si představíš jako polynom, ten vynásobíš x^10, pak to vydělíš uvedeným polynomem, vezmeš zbytek po dělení, přičteš k němu něco a máš kontrolní součet.

Hlavně si nastuduj, jak se dělí polynomy. To je normální matematika.

[msar]

Díky za pohotové reakce. Už je mi to jasnější, ale ještě jsem to úplně nepochopil. Budu muset trochu studovat...
Připadá mi, že na dekodovaní je potřeba sálový počítač a jestli to půjde nacpat do Atmela ...
Polynom je mnohočlen, ne?

EDIT: Celá norma je na http://wiki.tux-project.de/images/d/d2/ ... andard.pdf Je to pravda s přílohami, ANNEX A str.59 a ANNEX B str.60
Takže 16bitů jako polynom, vynásobit x^10, vydělit modulo 2 a zbytek po dělení sečíst modulo 2 s 10bit slovem z ANNEXU A. ?

[stepa]

Polynom je mnohočlen, ne?

Na toto jsem schopny odpovedet, ano polynom a mnohoclen je totez.

[Radix]

Ještě známe třeba polygamii.

[Piitr]

Připadá mi, že na dekodovaní je potřeba sálový počítač a jestli to půjde nacpat do Atmela ...

Neboj, algoritmus je zcela triviální.

Polynom je mnohočlen, ne?

Jo jo.

Takže 16bitů jako polynom, vynásobit x^10, vydělit modulo 2 a zbytek po dělení sečíst modulo 2 s 10bit slovem z ANNEXU A. ?

Přesně tak.

Algoritmus dělení:
Máš proměnnou "z" dlouhou 16 bitů. (Stačilo by i 10, ale líp se dělá s 2 bajty.) To bude zbytek po dělení. Na konci v něm bude výsledek.
Máš proměnnou/konstantu "poly" dlouhou 16 bitů. (Zase by stačilo jen 10.) V ní bude ten polynom, kterým dělíš. Bude v ní "10110111001".
Postupně budeš číst data bit po bitu. Začneš nejvyšším. Projdeš postupně celých 26 bitů dat (16 jsou data, 10 jsou jen nuly).
1) Do "z" dáš nulu.
2) Do "carry" načteš další bit dat.
3) Uděláš "rol z". Tzn. z se posune doleva, nejvyšší bit vypadne do carry, původní carry vleze do nejnižšího bitu.
4) Testuješ bit 2^10 proměnné "z". (Pokud bys měl to "z" jen na 10 bitů, tak už bys tam tenhle bit neměl, takže bys testoval carry.) Pokud je ten bit roven 1, pak uděláš "xor z, poly" (výsledek se ukládá do "z").
5) Pokud máš ještě nějký bit dat, jdi na bod 2. Jinak končíš a v "z" máš zbytek po dělení. Ještě bys k němu měl přičíst tu konstantu z annex a.

Je to strašně jednoduchý. Klidně to lze počítat postupně, rovnou jak ta data přicházejí z éteru.
Ten algoritmus nahoře jde použít pro vygenerování toho kontrolního slova. Ale pokud chceš jen kontrolovat, že jsou data i s kontrolním slovem dobře, stačí to takhle:
Algoritmem výše proženeš celých 26 přijatých bitů, včetně toho kontrolního slova. Pokud ti výsledný zbytek po dělení (ještě před odečtením slova z annex a) vyjde stejný jako ten offset z annexu a, tak je to dobře. Pokud vyjde něco jiného, je to špatně a došlo k chybě při přenosu.

Ono by teoreticky asi šlo jednu nebo 2 chyby i opravit, ne jen poznat, že je to špatně, ale to už je složitější.

[Piitr]

Ještě upřesnění pro jistotu: Tím "přičíst konstantu z annex a" nebo "odečíst ..." se samozřejmě myslí udělat XOR, protože počítáme modulo 2.

[Piitr]

Ještě známe třeba polygamii.

Nebo polikliniku.

[Cust]

doporucuju se mrknout do skriptarny technickych skol (elektro) a poridit si publikaci, skripta to maji popsane dopodrobna a kdyz si zakryjes tu teorii, tak i polopaticky (nekdy i s algoritmama)
popripade na netu hledej cyklicke redundantni kodovani (CRC), popripade polynomialni

[msar]

Zatím programuju s AT řady 89 a tam jsou bajtový proměnný, tak budu muset dávat dva dohromady pro 16 bitů.
Ještě dotaz: Proč testovat bit 2^10 proměnné "z" ? Pochopil jsem to tak, že si do "z" nahraju přijatých 16bitů, z nich vypočítám kontrolní 10bitové slovo a to porovnám s 10 bity co jsem přijal a jestli to bude stejné výsledek je platný.
Ještě dotaz: Proč musí být ten bit (2^10) roven 1? Počítám jen s 11bity z 16bitového slova? (když dělím 11bit číslem 10110111001)

[Piitr]

Zatím programuju s AT řady 89 a tam jsou bajtový proměnný, tak budu muset dávat dva dohromady pro 16 bitů.

Přesně tak. Já to nerozepisoval z důvodu přehlednosti.

Ještě dotaz: Proč testovat bit 2^10 proměnné "z" ?

To odvození algoritmu je na delší povídání. Nerad bych se do toho pouštěl. Tím porovnáním vlastně dělíš nejvyšší řády těch polynomů a tím zjistíš, zda má jít do výsledku 0 nebo 1. Je to obdoba dělení čísel na papíře, jak umíš ze školy.

Pochopil jsem to tak, že si do "z" nahraju přijatých 16bitů,

Celkem tam musíš nacpat 26 bitů. Místo kontrolního součtu tam cpeš 10 nul. To "nahraju" není úplně přesné. Jak tam ty bity nasouváš, tak se hodnota mění. V každém kroku bude nenulových pouze 10 bitů "z".

z nich vypočítám kontrolní 10bitové slovo a to porovnám s 10 bity co jsem přijal a jestli to bude stejné výsledek je platný.

Tak to lze dělat. Ale jednodušší je to, co jsem psal na konci. Do "z" nasuneš celých 26 bitů i s kontrolním součtem a pak jen otestuješ jestli je v "z" ta hodnota z annex a.

Ještě dotaz: Proč musí být ten bit (2^10) roven 1? Počítám jen s 11bity z 16bitového slova? (když dělím 11bit číslem 10110111001)

Nasuneš tam dokonce 26 bitů. Ale vždy, když je bit 2^10 jedničkový, zase ho tím XOR vynuluješ, takže v "z" máš pořád jen 10 bitů. To tak musí být, protože to je zbytek po dělení - musí být menší než dělitel.

[Piitr]

Hele, napsal jsem ti takovou ukázku v céčku pro PC. Třeba ti to pomůže.

Kód: Vybrat vše

#include <stdio.h>

/* prelozeno v MinGW, tam je short na 16 bitu a long na 32 */
typedef unsigned short U16;
typedef unsigned long U32;

U16 poly = 0x5B9; /* 101 1011 1001 */
U16 off = 0x0FC; /* 00 1111 1100 */

/* Spocita zbytek po deleni a vrati ho. */
U16 spocitej_zbytek(U32 delenec)
{
   U16 z, bit;
   int i;
   
   z = 0; /* nuluju z */
   for ( i = 25; i >= 0; i-- ) /* pro vsechny bity od nejvyssiho */
   {
      bit = delenec >> i & 1; /* vyberu bit 2^i */
      z = z << 1 | bit; /* nasunu bit do z */
      if ( z & 1 << 10 ) /* je-li bit 2^10 jednicka */
      {
         z ^= poly; /* XORujeme z polynomem, tim se jednicka shodi */
      }
   }
   
   return z;
}

/* Doplni do bloku soucet a vysledny blok vrati. */
U32 dopln_soucet(U32 blok)
{
   U32 vysledek;
   U16 soucet;
   
   vysledek = blok; /* vezmu blok */
   vysledek &= ~((1 << 10) - 1); /* nuluju poslednich 10 bitu */
   soucet = spocitej_zbytek(vysledek) ^ off; /* spocitej soucet */
   vysledek |= soucet; /* misto poslednich 10 bitu dam soucet */
   
   return vysledek;
}

/* Vraci nenulu, kdyz ma blok v poradku soucet */
int testuj_soucet(U32 blok)
{
   U16 zbytek;
   
   zbytek = spocitej_zbytek(blok);
   
   return zbytek == off;
}

int main(int agrc, const char **argv)
{
   U32 data;
   
   /* nejaka data, soucet samozrejme nesedi */
   data = 0x35ABC00;
   printf("1) %lX - %i\n", data, testuj_soucet(data));
   
   /* doplnime soucet, soucet by mel sedet */
   data = dopln_soucet(data);
   printf("2) %lX - %i\n", data, testuj_soucet(data));
   
   return 0;
}

[msar]

Ale vždy, když je bit 2^10 jedničkový, zase ho tím XOR vynuluješ, takže v "z" máš pořád jen 10 bitů.

To jsem potřeboval vědět, teď už mi je to jasné Céčku bohužel nerozumím, programuju v assembleru. Zkusil jsem napsat program, kde přijmu 26bitů a vypočítám kontrolní slovo, přijmu následujících 26bitů a vypočítám totéž. S tím, že kdyby se rovnaly, tak jsem zachytil správnou informaci. Oboje zobrazím na LCD, ale místo prvního kontr. slova se zobrazí samé 1 (někde mám chybu) a druhé kontr. slovo zobrazuje různá 10 bit čísla, což by mohlo být správné.

[Piitr]

Když sem dáš ten kód, kouknu se na to. Já s 51 nedělám, takže ti program nenapíšu, ale číst bych to asi mohl, protože na jiné procesory v assembleru píšu.