[Alg] Infrarood codes decoderen

[-DarkShadow-]

Ik krijg van een infrarood ontvanger een array binnen waaruit ik een bepaalde code moet herkennen, ik zoek hiervoor een algoritme. Voorbeeld:

Array: 6, 8, 18, 8, 5, 8, 19, 8, 5, 8, 18, 9, 18, 7, 6, 8, 5, 8, 5, 8, 19, 8, 5, 7, 19, 9, 5, 7, 6, 8, 18, 8, 19, 8, 18, 8

De code die ik hieruit zou moet halen is: 5, 8, 19, 8

Door storing is de array nooit hetzelfde, een ideale array zou er als volgt uitzien: 5, 8, 19, 8, 5, 8, 19, 8, 5, 8, 19, 8, 5, 8, 19, 8...

Ik weet van te voren niet welke codes ik kan verwachten, want de IR ontvanger doet het op alle afstandsbedieningen. Ik wil wel zo nauwkeurig mogelijk de code te weten komen. De array kan 256 waarden lang zijn, maar ook slechts 8. In dat laatste geval is de herkenning natuurlijk minder betrouwbaar.

Aan wat voor algortimes moet ik denken? Hoe moet ik dit aanpakken? Hoe wordt dit normaal gesproken gedaan? Zoekwoorden?

De code is de code die een IR afstandsbediening uitzendt. Ik weet niet of er afspraken over deze codes zijn, of dat er speciale algoritmes voor zijn. Dat heb ik niet kunnen vinden.

[ Voor 10% gewijzigd door -DarkShadow- op 27-07-2005 12:44 . Reden: Voor Zoijar \/ \/ \/ \/ \/ \/ ]

[Zoijar]

Begin eens te vertellen wat die codes precies voorstellen? Zijn het foutcorrigerende polynomen oid? Goed... dus je hebt een rij getallen, en daar wil je een deelrij uithalen... Ik zou zeggen neem de 1e 4e 7e en 10e...:P

[ Voor 38% gewijzigd door Zoijar op 27-07-2005 12:56 ]

[rrrandy]

Is de code altijd een reeks van een vast aantal getallen? Dan kun je je array opdelen in stukjes zo groot als de reeks die je moet hebben en dan voor iedere positie in de reeks kijken welk getal er het vaakst voorkomt. Grote kans dat je dan die moet hebben.

[samo]

Zijn die codes altijd van laag naar hoog of is dat ook random? Anders weet je makkelijk wanneer een herhaling van de code begint.

[Zoijar]

Een herhalingscode is in principe een lineaire code. Je kan dus met een check matrix etc werken, en dan een woordenboek van syndromen bijhouden. Maar gezond verstand zegt je ook al dat je net zo goed om de 4 getallen kan kijken, en van welk getal er dan het meest zijn, dat is met de grootste kans het getal dat je zoekt. Wat rrrandy dus al zei.

Dus voor 4 getallen, met 3x herhaling, wordt de string 1234 omgezet naar 1234-1234-1234, als je dan 1734-8239-1264 binnen krijgt, dan heb je op de "eerste plek" 1-8-1 dus dat moet een 1 zijn, op de tweede plek 7-2-2, dus een 2, 3e plek 3-3-6 dus 3, 4e plek 4-9-4 dus 4. String wordt 1234.

Dit is niet echt een ideale code. Als je namelijk n-keer herhaald, dan verbetert de code nog steeds maar weinig fouten (1 bij 3x, 1 bij 4x, 2 bij 5x,) etc. Het voordeel is wel weer dat fouten vaak als burst-errors optreden, dus heel veel achter elkaar, en dan weer een tijd goed. Bij dit soort fouten verbetert de code veel meer fouten.

[ Voor 5% gewijzigd door Zoijar op 27-07-2005 14:18 ]

[-DarkShadow-]

Zoijar schreef op woensdag 27 juli 2005 @ 14:15:
^^^^

Ik heb nog niet naar de check matrix methode gekeken, maar met de in dit genoemde topic oplossing wordt geen rekening gehouden met de storing. Zo worden er ook nummers overgeslagen, als je iedere vier nummers kijkt wat de code is en er mist een nummer, dan veranderd de code. De methode van rrrandy werkt dus niet.

samo-arne schreef op woensdag 27 juli 2005 @ 13:26:
Zijn die codes altijd van laag naar hoog of is dat ook random? Anders weet je makkelijk wanneer een herhaling van de code begint.

Volgens mij is het random.

Het is ingewikkelder dan het lijkt, maar daarom vraag ik het ook hier

[ Voor 37% gewijzigd door -DarkShadow- op 27-07-2005 14:29 ]

[ATS]

Een probleem dat je wel over blijft houden is dat je geen mogelijkheid hebt om uit te vinden wat de start van je sequence zou moeten zijn. In jouw voorbeeld kan je dus net zo goed 19 8 5 8 vinden. Tenzij je nog meer informatie hebt die je kan gebruiken?
Je zou misschien ook eens kunnen kijken hoe andere programma's dit doen. Er zijn wel Open Source programma's die dit doen, dus je hebt wat broncode ter beschikking...

[ Voor 25% gewijzigd door ATS op 27-07-2005 14:33 ]

[-DarkShadow-]

ATS schreef op woensdag 27 juli 2005 @ 14:32:
Een probleem dat je wel over blijft houden is dat je geen mogelijkheid hebt om uit te vinden wat de start van je sequence zou moeten zijn. In jouw voorbeeld kan je dus net zo goed 19 8 5 8 vinden. Tenzij je nog meer informatie hebt die je kan gebruiken?

Ja, maar dat is niet erg. Als ik maar iedere keer op dezelfde code uitkom.

[netvor]

Zitten die storingsfouten altijd tussen de codes in, of ook binnen de codes?

Tussen de codes in: 5 8 19 8 3 7 22 789 5 245 5 8 19 8 6 3 4 76 12 5 8 19 8
In dit geval is het makkelijk, gewoon kijken welk patroon met lengte 4 het meest voorkomt. Kost je wel een berg geheugen, maarja.

Binnen de codes: 5 8 19 5 8 5 8 6 19 8 8 5 8 19 8
Dit is al een heel stuk moeilijker, je zal moeten kijken welke transities vaker voorkomen, en hopelijk vind je dan dat de transities 5->8, 8->19, 19->8 en 8->5 het vaakst voorkomen.

EDIT
In any case scheelt het heel veel als je de lengte van de codes vooraf weet. Dus: weet je de lengte? weet je waar de storing zit? wat weet je wel, wat weet je niet?
In signal processing is het een kwestie van werken met wat je krijgt, en de belangrijkste stap is weten wat je wel en wat je niet krijgt.

[ Voor 24% gewijzigd door netvor op 27-07-2005 15:03 ]

[Bosmonster]

Is het een idee om gemiddeldes te berekenen van iedere waarde in de code? Zo zou je (hoe langer de reeks, hoe nauwkeuriger uiteraard) redelijk dicht in de buurt moeten kunnen komen van de waarden zoals ze bedoeld zijn.

De lengte van de code weten is daarbij wel een vereiste.

Transities bekijken lijkt me een ondoenlijke zaak, zeker als de storing relatief vaak optreedt per code (beide kanten van de transitie kunnen compleet verschillen en bij zulke kleine marges kan je dan aardig de fout in gaan denk ik)

[ Voor 30% gewijzigd door Bosmonster op 27-07-2005 15:10 ]

[Zoijar]

imp schreef op woensdag 27 juli 2005 @ 15:00:
Tussen de codes in: 5 8 19 8 3 7 22 789 5 245 5 8 19 8 6 3 4 76 12 5 8 19 8
In dit geval is het makkelijk, gewoon kijken welk patroon met lengte 4 het meest voorkomt. Kost je wel een berg geheugen, maarja.

Fouten corrigeren uit codes is sowieso een NP probleem, dus dat is geen punt...of juist 'het' punt, maar er is weinig aan te doen behalve slimme bestaande codes te gebruiken.

Voor de TS, je zal toch echt meer informatie moeten geven. Volgens mij weet je zelf niet eens wat je binnen krijgt, hoe moeten wij dan zeggen hoe je het moet decoderen?

[farlane]

Zorg dat je de timing van de codes weet zodat je de frames kunt onderscheiden

[-DarkShadow-]

De oplossing:

Ik ga ervanuit dat de code altijd 4 cijfers lang is. Dan neem ik een aantal samples van 4 lang uit de array. Die samples schuif ik langs de array en vergelijk ik met de array, een kleine afwijking mag bestaan. De sample die het meest overeenkomt is de waarschijnlijke code. Hoe meer samples er genomen worden en hoe kleiner de toegestane afwijking des te groter de kans de juiste code te vinden. Op deze methode zijn natuurlijk verschillende variaties mogelijk, zo zou je met een ander algoritme bijvoorbeeld eerst de lengte van de code kunnen berekenen. Dat is niet zo moeilijk.

Als dit bitneukend in C wordt geschreven, dan is het nog redelijk snel ook.

[MSalters]

Als je weet dat het gaat om een code van 4 tekens zonder bijzondere informatie over de verstoring is het triviaal. Zoijar's eerste reactie is dan overduidelijk de beste. Je fouttermen e_i en e_j correleren niet voor i != j. Het eerste teken uit de reeks is dan het gemiddelde van 1,5,9,etc, de 2e het gemiddelde van 2,6,10,...

Weet je de codelengte niet, dan is het nauwelijks moeilijker. Laat een FFT los op je dataset, pak de piek (die hier ongeveer een factor 100 hoger is dan 3 of 5, gok ik) uit je FFT en je weet het aantal elementen in je input (werkt zelfs als dat geen integer aantal is!)

Met burstfouten en volledig verlies van informatie heeft Zoijar weer gelijk, dan gebruik je geen gemiddelden maar medianen. Indien beide soorten fouten voorkomen, dan meng je ook die twee algoritmen: gooi outliers weg en middel de overgebleven data.

In serieuze toepassingen bepaal je natuurlijk eerst je (statistische) fouteigenschappen vorodat je een foutcorrectie algoritme bedenkt.

[Zoijar]

MSalters schreef op woensdag 27 juli 2005 @ 20:34:
Weet je de codelengte niet, dan is het nauwelijks moeilijker. Laat een FFT los op je dataset, pak de piek (die hier ongeveer een factor 100 hoger is dan 3 of 5, gok ik) uit je FFT en je weet het aantal elementen in je input (werkt zelfs als dat geen integer aantal is!)

Leuke oplossing; had ik nog niet aan gedacht

[H!GHGuY]

hmm, waarom zo moeilijk maken
beetje gezond verstand zorgt ook al voor iets wat kan helpen:

1) gebruik een frequentietabel om de meest voorkomende getallen te vinden (dan weet je ook meteen hoeveel et er zijn)
2) loop opnieuw door je reeks en bepaal de volgorde waarin de reeks voorkomt

dis weliswaar een O(n) op alle vlak (kort door de bocht erop geplakt ) maar met zo'n kleine dataset en de GHz'en van vandaag is zoiets een fluitje van een cent...

[netvor]

MSalters schreef op woensdag 27 juli 2005 @ 20:34:
Weet je de codelengte niet, dan is het nauwelijks moeilijker. Laat een FFT los op je dataset, pak de piek (die hier ongeveer een factor 100 hoger is dan 3 of 5, gok ik) uit je FFT en je weet het aantal elementen in je input (werkt zelfs als dat geen integer aantal is!)

FFT zou ik niet aanraden. TS zei namelijk dat de array soms slechts 8 samples lang is. FFT over 8 samples geeft niet heel veel informatie. In MATLAB:

code:

>> abs(fft([5 8 19 86 5 8 19 8 0]))

ans =

  Columns 1 through 7 

           86            6       35.023            6       17.475            6       17.475

  Columns 8 through 10 

            6       35.023            6

De piek zit dus op de derde kolom oftwel index 2 (afgezien van de "DC offset"), wat lengte 5 (10/5=2) zou geven! FFT is een mooie O(n log n) manier om de frequentie van je patroon te vinden, maar met slechts een beperkt aantal periodes (in dit geval 2) kan je er niet veel mee.

[Verwijderd]

Wat nou als de juiste waarde helemaal niet voorkomt? Volgens mij moet je niet op byte niveau maar (per byte) op bit niveau kijken. Dus pas het truukje van de hoogste frequentie toe op 1 enkele bit. Zo zou je theoretisch ook het juiste getal kunnen achterhalen als deze zelf niet in het rijtje voor komt.

Ik las ook iets over een voorstel tot het gebruik van gemiddelden, dat lijkt mij niet handig als bijvoorbeeld het most significant bit verkeerd over komt.

[ Voor 21% gewijzigd door Verwijderd op 28-07-2005 11:00 ]

[MSalters]

imp schreef op donderdag 28 juli 2005 @ 10:32:
[...]


FFT zou ik niet aanraden. TS zei namelijk dat de array soms slechts 8 samples lang is. FFT over 8 samples geeft niet heel veel informatie. In MATLAB:

code:

>> abs(fft([5 8 19 86 5 8 19 8 0]))

De piek zit dus op de derde kolom oftwel index 2 (afgezien van de "DC offset"), wat lengte 5 (10/5=2) zou geven!

Je voert een FFT op 9 samples uit, met 1 outlier (86)? Die 0 op het einde is ook verdacht. Bereken eens
abs(fft([5 8 19 8 5 8 19 8])).

[MSalters]

HIGHGuY schreef op woensdag 27 juli 2005 @ 21:45:
hmm, waarom zo moeilijk maken
beetje gezond verstand zorgt ook al voor iets wat kan helpen:

1) gebruik een frequentietabel om de meest voorkomende getallen te vinden (dan weet je ook meteen hoeveel et er zijn)
2) loop opnieuw door je reeks en bepaal de volgorde waarin de reeks voorkomt

dis weliswaar een O(n) op alle vlak (kort door de bocht erop geplakt ) maar met zo'n kleine dataset en de GHz'en van vandaag is zoiets een fluitje van een cent...

Ik vermoed dat Zoijar ook signaalverwerking heeft gehad in zijn opleiding. Jouw oplossing gaat fout als er in je signaal een waarde twee keer voorkomt (tenminste, dat denk ik - je algoritme is niet echt formeel).
Vb. Met een signaal [10 5 5 0] kloppen je frequenties niet. Dit wordt echt erg als je een signaal hebt als [10 5 5 6] met een gemiddelde fout van 1.0

[netvor]

MSalters schreef op donderdag 28 juli 2005 @ 11:33:
[...]

Je voert een FFT op 9 samples uit, met 1 outlier (86)? Die 0 op het einde is ook verdacht. Bereken eens
abs(fft([5 8 19 8 5 8 19 8])).

Hmm, die 86 is het resultaat van React die mijn spatie heeft opgegeten . net nog even in mijn matlab history gekeken en ik had toch echt [5 8 19 8 6 5 8 19 8 0] ingevoerd, dus zeg maar 2x de basisserie (5 8 19 8 ) plus twee errors, lijkt me reeel. De nul op het einde moet kunnen; ik neem aan dat de IR ontvanger een array van UINT's opstuurt, dus dan is een 0 een van de mogelijkheden.
Trouwens, de fft van [5 8 19 8 5 8 19 8] gaat wel goed, maarja, die heeft dan ook geen errors.

[MSalters]

Lijkt me dus een bewijs dat het FFT algoritme werkt, je sequence lengte is 5: [5 8 19 8 ?] en je FFT geeft een lengte 5, ondanks de 2 fouten.

[hobbit_be]

een beetje wild idea maar een mogelijke oplossing is een compressie programma/algo gebruiken. normaal zouden veel voorkomende sequences daar dan toch in een tabel moeten terecht komen. geen idee van details maar dacht dat de meeste technieken zo werkten.

[grizzlybear]

Misschien een idee om te kijken hoe dit in Lirc gedaan wordt?

[ Voor 21% gewijzigd door grizzlybear op 28-07-2005 14:21 ]

[netvor]

MSalters schreef op donderdag 28 juli 2005 @ 13:30:
Lijkt me dus een bewijs dat het FFT algoritme werkt, je sequence lengte is 5: [5 8 19 8 ?] en je FFT geeft een lengte 5, ondanks de 2 fouten.

Ja, de FFT doet precies wat hij moet doen...maar helaas is dat niet wat we willen, namelijk de lengte van een code uitvogelen. FFT geeft ons dus eigenlijk de lengte van een code + de gemiddelde lengte van de serie fouten tussen de codes. Bijvoorbeeld [5 8 19 8 6 5 8 19 8 5 8 19 8 0 5 8 19 8] (dus 4 codes, 2 errors) geeft mij lengte 4.5...tsja, dan wordt het afronden.

[Verwijderd]

Ik snap nog steeds niet waarom er wordt gepoogd de juiste waarde te achterhalen aan de hand van een numerieke waarde van een setje bitjes. Dat is gewoon domweg fout, zo'n getal zegt je namelijk helemaal niets:
1011 (bin) = 11 (dec)
0011 (bin) = 3 (dec)
Je kunt dus domweg niet werken met gemiddelden, het vertelt je immers niets nuttigs. Enkel de frequencie van een getal zou een correcte aaname zijn dat je met de juiste waarde te maken hebt. Daarom blijf ik erbij dat je met bitjes moet werken en niet met numerieke waarden:

verwachte waarde
1011 (bin) = 11 (dec)

ontvangen waarde
0011 (bin) = 3 (dec)
1010 (bin) = 10 (dec)
1001 (bin) = 9 (dec)

aan de hand van bit frequencie zou je nu 1011 krijgen en dus de correcte waarde. Ik vraag me af hoe je dit uit de numerieke representatie wilt herleiden.

[ Voor 5% gewijzigd door Verwijderd op 28-07-2005 14:59 ]

[The Bad Seed]

imp schreef op donderdag 28 juli 2005 @ 14:29:
[...]


Ja, de FFT doet precies wat hij moet doen...maar helaas is dat niet wat we willen, namelijk de lengte van een code uitvogelen. FFT geeft ons dus eigenlijk de lengte van een code + de gemiddelde lengte van de serie fouten tussen de codes. Bijvoorbeeld [5 8 19 8 6 5 8 19 8 5 8 19 8 0 5 8 19 8] (dus 4 codes, 2 errors) geeft mij lengte 4.5...tsja, dan wordt het afronden.

Het probleem van de fouten bij een IR afstandsbediening is niet of er al dan niet randomwaarden tussen de reeksen ingegooid worden zoals in jouw voorbeeld, maar dat niet elke bit perfect aankomt. Tenminste dat is hetgeen ik me herinner van het prutsen met een afstandsbediening, een IR ontvangertje en een digitale scoop. Helaas heb ik hier thuis niet zo'n scoop staan, dus dat kan ik nu niet proberen.
Een FFT zou dus wel moeten werken

[netvor]

The Bad Seed schreef op donderdag 28 juli 2005 @ 15:11:
[...]
Het probleem van de fouten bij een IR afstandsbediening is niet of er al dan niet randomwaarden tussen de reeksen ingegooid worden zoals in jouw voorbeeld, maar dat niet elke bit perfect aankomt. Tenminste dat is hetgeen ik me herinner van het prutsen met een afstandsbediening, een IR ontvangertje en een digitale scoop. Helaas heb ik hier thuis niet zo'n scoop staan, dus dat kan ik nu niet proberen.
Een FFT zou dus wel moeten werken

Tsja...het probleem is dus dat de TS niet genoeg informatie over zijn apparaat gegeven heeft. Ikzelf dacht dat de ontvanger meer een soort DTMF decoder is, in de zin dat ie het signaal analyseert, demoduleert tot een discrete set symbolen (in het geval van DTMF bijvoorbeeld 16), en die symbolen naar de host stuurt als een array.

[-DarkShadow-]

Het probleem in de TS is niet meer relevant De code zit er namelijk op een andere manier in verstopt. Ik ben nog aan het uitzoeken hoe precies, maar ik ben er bijna.

De oplossingen die hier worden gegeven zijn leuk, maar ik denk niet wanneer ze 50 keer per seconde moeten worden toegepast. (en de processor niet te veel mogen belasten) \/ \/ \/

Ik heb de broncode van WinLIRC eens doorgenomen, maar die pakken het aan met configuratiebestanden en andere luxe dingen. In de tijd dat ik die source heb uitgevogeld kan ik het zelf ook wel uitvogelen. (wat een gevogel )

Nog even over de code:

code:

6 8 18 8 5 8 19 8 5 8 18 9 18 7 6 8 5 8 5 8 19 8 5 7 19 9 5 7 6 8 18 8 19 8 18 8 =
0 0  1 0 0 0  1 0 0 0  1 0  1 0 0 0 0 0 0 0  1 0 0 0  1 0 0 0 0 0  1 0  1 0  1 0

En daar moet dan weer een code uitgehaald worden. De binaire code bestaat uit een wisselend en een constant deel. Dat constante gedeelte moet ik er uit filteren. Er zijn verschillende decoderingen, maar ze lijken allemaal op bovenstaande.

[ Voor 3% gewijzigd door -DarkShadow- op 28-07-2005 18:32 ]

[MSalters]

imp schreef op donderdag 28 juli 2005 @ 14:29:
[...]
Ja, de FFT doet precies wat hij moet doen...maar helaas is dat niet wat we willen, namelijk de lengte van een code uitvogelen. FFT geeft ons dus eigenlijk de lengte van een code + de gemiddelde lengte van de serie fouten tussen de codes. Bijvoorbeeld [5 8 19 8 6 5 8 19 8 5 8 19 8 0 5 8 19 8] (dus 4 codes, 2 errors) geeft mij lengte 4.5...tsja, dan wordt het afronden.

We gaan er van uit dat er geen fouten tussen codes zitten. Dat zou ook wel vreemd zijn. Waarom zouden die fouten nou net tussen codes zitten? En hoe komen die fouten daar? Time warps komen echt alleen in Star Trek voor. Een synchrone ontvanger heeft die problemen niet. Ik mag hopen dat de TS niet te maken heeft met een asynchrone set samples, dan heeft hij een veel groter probleem.

[MSalters]

-DarkShadow- schreef op donderdag 28 juli 2005 @ 17:01:
De oplossingen die hier worden gegeven zijn leuk, maar ik denk niet wanneer ze 50 keer per seconde moeten worden toegepast.

Ik hoop dat je bedoelt: 50 miljard keer per seconde. 50 keer per seconde haal je nog op een ondergeklokte XT die naar floppy disk moet swappen.