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.