Protocol ontwerpen

Het idee is je wel duidelijk geloof ik.

Je hebt nu alleen geen adressering. Als je zeker weet dat er nooit een andere zender (of ontvanger) bij komt (ook niet van een andere gebruiker), dan kan dat. Maar het is een kleine moeite.

De checksum is een beetje breekbaar. Je zou iets degelijkers kunnen gebruiken, zoals bijv. de CRC van X25. Die is veel bomvaster.

/e: 115kb op 850 .. 1000 kHz draadloos, dat wordt nog een hele klus. Dat is procentueel nogal een bandbreedte. En je weet dat daar ook al andere gebruikers zitten?

Wat als nu je pariteitsbit ook een error heeft zoals FET zegt. Dan kan een byte goed lijken, maar dan zitten er toch fouten in.

Ik wil zelf (niet voor school) ook nog eens zoiets doen. Nouja, niet een heel protocol, maar een draadloze verbinding die het volgende doet:

microconroller met data ingang (serieel), en een lijntje waarmee 'ie aangeeft of er data in mag.
aangeven dat er data in mag, tijdelijk opslaan, komt er geen data meer of is de buffer vol: lijntje dat er geen data meer in mag hoog maken. ' t ding wat de data aanlevert moet daar maar naar luisteren, de microcontroller neemt geen data meer en gaat rekenen.

microcontroller past hamming(7,4) toe op elke nible data (op die manier kan de ontvanger foutcorrectie doen), doet vervolgens manchester encoding (alle 1en worden 10, alle 0llen worden 01). 433mhz zendertjes vinden meerdere 1en en 0llen achter elkaar namelijk zodanig niet-leuk, dat ze niet doorkomen.

Microcontroller duwt deze data (elke nibble is nu dus al 14 bits) door een zender. en geeft weer aan dat er data in mag

Ontvangende kant buffert eerst, decodeert dan de manchesterencoding, doet dan foutcorrectie, en spuugt daarna de data weer serieel uit.

Ga er niet op wachten, het zou wel een héél lang kunnen duren voor ik dit af heb... Misschien komt het zelfs nooit af*. Maar misschien zitten er in mijn plan van aanpak nog dingen waar je wat hebt. Foutcorrectie bijvoorbeeld, zou handig kunnen zijn.

EDIT:

Op 6 mei 2009 15:56:55 schreef Frederick E. Terman:
De checksum is een beetje breekbaar. Je zou iets degelijkers kunnen gebruiken, zoals bijv. de CRC van X25. Die is veel bomvaster.

Ik ben ook zeer geintereseerd in methoden tot foutcorectie. Is er iets makkelijkers/simpelers/beters (en liefst alle 3) dan hamming(7,4)? (er was ook hamming(8,11) dacht ik, dan zou je per byte kunnen versleutelen) Mocht ik ooit nog aan mijn betrouwbare draadloze datalinkproject toekomen (zit nu vlak voor de examens, dus drukdrukdrukdrukdruk). Enige wat ik tot nu toe aan " bruikbaars " ben tegengekomen is de wikipagina over hammingcode. Maar er zijn natuurlijk meer methodes.

*=_{ben er nu (29-jun-2009) aan begonnen en het is nog niet af, maar wel al heel erg traag. Dus je moet meer in de richting van bytes per minuut gaan denken dan bits per seconde... Goede kans dus dat dit project niet wordt voortgezet.
Aanvulling: Het is nu 13 juli, ik ben toch aan dit projectje doorgegaan, en hoewel de opzet iets gewijzigd is ziet het er naar uit dat het toch gaat lukken. Niet bijster snel misschien, maar wel error correctie voor 1 bit per nibble (dus 2 bits per byte, maar ze mogen niet in hetzelfde nibble zitten). Code is nog niet af, maar de belangrijkste dingen (hamming encode, foutcorrectie, hamming decoden) werken.}

Ik had het zelfs alleen nog maar over foutdetectie. Fout CORrectis is ook heel prettig natuurlijk. Omdat je alleen één kant op werkt (er is geen retourkanaal), noem je dat Forward Error Correction, FEC dus. Daar zou je op kunnen zoeken.
Er zijn heel krachtige codes bij. Het hangt wel een beetje van de soort storing af die je verwacht wat er handig is.
Heb je een continue ruis, waardoor er steeds op de gekste plaatsen één bitje verminkt? Of heb je bursts van storing, waardoor af en toe hele groepen bits verminkt worden?
Als je dat weet, kun je de codering overeenkomstig kiezen.

Een paar jaar terug was Golay code erg in de mode. Maar er zijn er meer.

In principe is er maar een zender en een ontvanger. Er zijn wel meerdere groepjes aan het werk, die waarschijnlijk allemaal ongeveer dezelfde frequentie gebruiken, maar ik zie niet in waarom adressering daarin een voordeel kan zijn: ik heb sowieso al een unieke start- en stopbyte.

Die CRC is inderdaad een goed idee. Het aantal bytes zal meestal niet boven de 10 uitkomen.
Kan ik CRC ook uitvoeren over het complete datapakket?
Dan kan ik dus parity bitjes én CRC gebruiken, of is dat overkill?

edit: als error correctie wou ik eigenlijk gewoon het complete pakket twee keer sturen.

Zoek eens op Ack/Nak protocol, dat is eigenlijk wat je beschrijft. Het is een ultrasimpel protocolletje dat met een paar regels code in een controller te implementeren is.
Let erop dat de STX niet meedoet in de BCC checksum berekening en de ETX wel. Je maakt van de lengte + de data een string.

probleem met FEC is volgens mij dat we over de seriële uitgang alleen per byte uit kunnen sturen. Dan zou ik dus iets anders moeten doen:
0 --> 0000
1 --> 1111
Als er de meeste nullen binnenkomen --> 0. Als er de meeste enen binnenkomen --> 1. Als er evenveel nullen als enen binnenkomen maak je er 0 of 1 van, weet ik veel.

Het zou dus betekenen dat de hoeveelheid data 4x zo veel wordt. Anders zou ik het sowieso 2x sturen voor de zekerheid.

Aangezien die hoeveelheid data laag is, komt het aantal bytes aan spul eromheen (start/stop) in de buurt van de aantal databytes en zal het qua besparing niet veel uitmaken of ik FEC doe, of alles twee keer stuur.

een bit meerdere keren achter elkaar sturen en dan kijken waarvan de meeste binnenkomen is ook foutcorectie. Om het even veel enen als nullen probleem op te vangen kun je de bit een oneven aantal keer sturen.

Houd er wel rekening mee dat een standaard 433mhz zendertje meerdere 1en of 0en achter elkaar niet goed doorstuurt. Ik weet niet of het voor jou zender ook geldt, maar er is een maximumtijd dat de ingang van zo'n ding hoog/laag mag zijn.

Op 6 mei 2009 17:32:24 schreef Lucky luke:
Houd er wel rekening mee dat een standaard 433mhz zendertje meerdere 1en of 0en achter elkaar niet goed doorstuurt. Ik weet niet of het voor jou zender ook geldt, maar er is een maximumtijd dat de ingang van zo'n ding hoog/laag mag zijn.

Daar kan je gewoon manchester encoding voor gebruiken, die zorgt voor de 1-0 wisselingen.

Ik zou het bij een CRC houden en het opnieuw verzenden wanneer er een CRC fout is. FECs als Turbo Codecs, Golay, Viterbi (voor ruis) of Reed-Solomon (voor error-bursts) decoders zijn niet in een 8bit micro te implementeren. Je hebt er vaak meer RAM voor nodig dan je micro heeft (OK: als je met ARM of zoiets werkt heb je daar geen last van).
Het zijn trouwens niet de meest simpele blokjes code, om van de wiskunde die erachter zit nog maar te zwijgen

Toch moet er wel iets leuks te maken zijn. De pakketjes zijn niet zo lang. Het gewone 4/3 schema (zie: CCIR 476) doet dan al bijzonder veel, en kost bijna niets aan processortijd of ruimte.

Gewoon ettelijke malen een 1 sturen om een enkele 1 aan te duiden is niet zo mooi. Met veel minder overhead kun je veel zekerder verzenden.

TS: als je een unieke startbyte gebruikt, dan is dat voor mij zoiets als adressering.. dus dat is geregeld.

Een combinatie van parity per teken (bijv. 4/3) en dan nog eens een CRC over het geheel kost niet veel extra; je kunt het gerust doen.

Ik zou trouwens in ieder geval even naar X25 kijken, want daar hoort ook bij dat je niet teveel 1 of teveel 0 achter elkaar verstuurt (zie: bit stuffing). Dat is hier ook nuttig ivm. de gebruikte HF blikjes, lees ik.

voor het eerste jaars TUE Elektroproject?

Wat, het concept dat je na 3 enen een nul toevoegt (omdat je anders teveel enen krijgt), en dat je dus aan de ontvangkant na 3 enen de daaropvolgende nul moet verwijderen?
Dat is toch niet zo'n mumbojumbo?

Op 6 mei 2009 19:30:03 schreef Frederick E. Terman:
Ik zou trouwens in ieder geval even naar X25 kijken, want daar hoort ook bij dat je niet teveel 1 of teveel 0 achter elkaar verstuurt

Ik doe iets dergelijks voor m'n sturing over het lichtnet:

Een header (4 enen)
Adres en data, waarbij een '1' verzonden wordt als "10" en een '0' als "01"
Een afsluiter (4 nullen)

Buiten de header kan je nooit meer dan 2 opeenvolgende enen ontvangen, en enkel de afsluiter kan meer dan 2 opeenvolgende nullen bevatten.
Al-met-al een eenvoudige methode, al durf ik niet garant staan voor de robuustheid in woelige wateren...

Op 6 mei 2009 20:06:58 schreef Frederick E. Terman:
Wat, het concept dat je na 3 enen een nul toevoegt (omdat je anders teveel enen krijgt), en dat je dus aan de ontvangkant na 3 enen de daaropvolgende nul moet verwijderen?
Dat is toch niet zo'n mumbojumbo?

Is dit geen HDB3?

X25 gebruikt HDLC. Hier in wordt bij asynchrone framing een 7E hex gebruikt als een syncbyte. Als je de 7E als data wilt versturen moet je een 7D versturen en dan de 7E. Als je 7D wilt versturen verstuur je 7D 7D.

Bij synchrone framing wordt er na 5 bits 1 een nul toegevoegd.

@ TS. Denk eerst na over wat je met het protocol wilt bereiken. Is het een zender en 1 ontvanger, of heb je 1 zender en meerdere ontvangers?

Kijk naar je toepassing.
Een protocol met een beperkte bandbreedte heeft een lage snelheid aan data. Je overhead van het protocol moet je zo klein mogelijk houden.

Hoe betrouwbaar moet het zijn. Mag je een pakket missen of is het missen van een pakket dodelijk voor je applicatie?

Bij meerdere ontvangers die selectief aangestuurd moeten worden, heb je een adressering nodig. Dit kan je ook in een laag hoger doen.

Communicatie protocollen zijn over het algemeen een stapel van protocollen.

Even je gegevens gerangschikt.
fysieke laag. Radiosignaal. 850~1MHz 115kbps

Datalink laag,
max 256 bytes. Maak hier 255Bytes van. Je lengte is maar 1 byte en 256 is 9 bits.
Voor je error detectie kan je beter een CRC of een FEC pakken. Is al eerder besproken in dit topic.
Start en stopbyte kan je gelijk houden. Noem het alleen een sync byte.
<SYNC>255data<SYNC>255data<SYNC>
Meerdere sync bytes achter elkaar is niet erg. en als je meer dan 255 bytes data hebt heb je toch weer een byte minder verstuurd.

Paar protocollen waar je wel wat bruikbare zaken uit kan slopen.

HDLC Er wordt in dit topic gezegd dat X25 iets doet met bitstuffing om niet te veel enen achter elkaar te zetten. Dit gebeurt echter in de HDLC layer.

navtex Hier zit een Forward Error Correcting Code in.

Tip voor het testen, Gebruik RS422 of RS485. Zet niet continue een zender in de lucht om te testen. Voor je protocol maakt het niet veel uit of je nu draadloos werkt of met draadjes.

Klopt, ik was slordig. HDLC bit stuffing is na 5 enen, niet na 3 al. Gelukkig blijft het idee hetzelfde.
X25 gebruikt HDLC.

Ik hintte al over de gebruikte frequentie (dat dat lastig zou worden), maar dat gaf nog geen reactie.
Hoe ga je dat doen, zenden met 115kb op die frequentie; en wat voor reikwijdte verwacht je/heb je nodig?

Oke, ik zal er nog wat info bijgeven:

FPGA (zender) kan maximaal 115kBd uitzenden. Dit is echter nu ingesteld op 9600 baud en kan nog wat bijgeschaafd worden.

Data komt uit de RS232 poort van de FPGA en moet ontvangen worden naar een RS232 poort van een laptop.

Er is één zender en één ontvanger, en die mogen we zelf maken. De frequentie zal zo rond de 1MHz liggen. Reikwijdte zal zo'n 10 meter worden.

Er zullen in praktijk per pakketje ca. 10 bytes verstuurd gaan worden.

CRC ga ik zeker toepassen.

Het is niet erg als er een pakketje verloren gaat. Ik wou in ieder geval alle data twee keer sturen voor de zekerheid. Error correctie zal ik me in gaan verdiepen.

We kunnen alleen complete bytes naar de RS232 poort sturen, geen losse bitjes.

En ja, het is voor het eerstejaars TU/e Elektroproject

In het eerste jaar was het 20 jaar geleden nog niet de bedoeling om complete FEC te gaan doen. Jou methode om alles 2x te sturen is dan een acceptabele manier om aan FEC te doen.

Mischien voor 3x sturen ipv 2x kiezen.

Mischien een "pakket-nummer" toevoegen. Dan weet je welke data pakketjes je al hebt gehad.

Of je het wel of niet in je eerste jaar doet, hangt meer van de volgorde van de stof af, dan van de moeilijkheid (je kunt natuurlijk heel ver gaan, maar het begin is werkelijk eenvoudig).

Als je uitgaat van herhaling en een parity, dan zit je al heel dicht bij 4/3 fec. Dat is een heel makkelijk te begrijpen methode (iedere "byte" moet 4 enen en 3 nullen hebben; er is een herhaling; de ontvanger kiest het onverminkte teken of merkt het teken als "fout" aan). Weer- en navigatieberichten worden zo uitgezonden. Het is beter dan 3x verzenden en toch simpel.

Een pakketnummering is een goede tip (dat doen ze met die navigatieberichten ook per bericht).

_{In dat 4/3 systeem bestaan er dus (vanwege die 7 bits) 128 mogelijke ontvangen symbolen, waarvan er maar 35 geldig zijn. Wil je meer verschillende tekens overbrengen, dan kun je dit natuurlijk uitbreiden.
'Gewone' parity werkt eigenlijk net zo: daar bestaan er 512 mogelijke ontvangen symbolen, waarvan er maar 256 geldig zijn.}

De truuk in flash chips is ook wel makkelijk toepasbaar...

Geef ieder bitje in je "data" een nummer. Daarna sla je op: parity(bits-waarvan-nummer-bit0 == 0), en parity(bits-waarvan-nummer-bit0 == 1), en zo voor alle andere bit-nummers. In een 512byte block in een flash chip, heb je 4096 bits, dus de nummers zijn 12 bits, dus er zijn 24 parity bits.

Dit detecteert-en-corrigeert alle 1-bits fouten. Het detecteert volgens mij alle twee-bits-fouten.

Op 7 mei 2009 09:00:54 schreef muddy:
We kunnen alleen complete bytes naar de RS232 poort sturen, geen losse bitjes.

Stel je seriële poort in op 8bits, 1 start 1 stop 1 parity odd of even en je kan 1 byte met parity versturen. Je FEC kan je daarnaast gewoon blijven gebruiken. Je UART kan dit gewoon voor je doen.

Dubbele check.

Wat ik al eerder schreef, een protocol moet je zien als een stapel protocollen. Als je elke laag een vorm van fout detectie en / of correctie geeft neemt je betrouwbaarheid toe.

[Bericht gewijzigd door jovak op donderdag 7 mei 2009 22:35:57 (24%)]

Voor het eerste jaars TU/e project hoef je nog niet zo diep er op in te gaan opzich, de radiolink is maar een klein onderdeel van het hele project, staar je hier niet dood op. Met een simpele CRC win je al veel bonuspunten. De werking daarvan leer je over een jaar in het vak Informatie en Communicatie theorie.

Ach, het klinkt ingewikkelder dan het is, zo'n CRC. Het is gewoon de rest bij deling door een bepaald getal.

Sommige zijn beter dan andere. Zo heeft het bijvoorbeeld weinig zijn door 128 te delen (bepaalde bits zouden dan altijd buiten schot blijven). Er zijn enkele heel goede getallen (allemaal priemgetallen) voor CRC's. Van die getallen is bekend dat je de kleinste kans loopt data met een fout toch 'goed' te keuren.
Kies er een, deel de data daardoor en bepaal de rest: dat is je CRC.

Als je erop gaat zoeken, kom je vaak het woord "polynoom" tegen.
Dan schrijven ze niet gewoon (bijvoorbeeld) 13, maar opeens x⁰ + x² + x³.
Toch gaat het dan gewoon om het getal 13.

Ah dáár staan die rare kwadraatjes voor Ik ga dat inderdaad toevoegen aan mijn protocol. Verder zijn we nu eerst de zender aan het bouwen: mocht het zo zijn dat deze heel veel storing meebrengt, voeg ik FEC toe, anders moet ik het nog even zien.

Ik ben in ieder geval al een heel stuk wijzer geworden, danku!

We zijn pas rond 20 augustus klaar, dus dan horen jullie het wel.

Een CRC is alleen leuk als je aan de zender kunt doorgeven dat een pakket niet juist ontvangen is.
In een simplex systeem heb je er dus niet veel aan.

Zoals een aantal van jullie weten ben ik druk doende met een nieuw boek.
Ditmaal geheel over praktische draadloze systemen.
Hierin beschrijf ik ook de FEC zoals de Hamming code.

De Hamming (7,4) heb ik uitgebreid naar Hiddink (8,4).
Dat ene bit heb ik gebruikt om het aantal achtereenvolgende '1'-en en '0'-en te verminderen naar 3.
Dat heeft weer voordelen voor de bitsynchronisatie van de draadloze verbinding.

Deze code heb ik uitgebreid geprobeerd en werkt uitstekend.

De microcontroller werkt met een LUT omdat je door het extra bit geen gebruik meer kunt maken van de mathematische eigenschappen van de Hamming code.

Stuur mij even een email als je het stukje tekst over de aangepaste Hamming in PDF wilt ontvangen.

Overigens is een compleet protocol veel meer dan alleen de fysieke laag.
Het hele protocol bevat ook zaken als collision detection, adressering, routing, etc.