www.mikrocontroller.net

Forum: Projekte & Code Even/Odd Parity berechnen


Autor: Rev (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Die Funktion berechnet das Parity-Bit für das übergebene Byte dataByte
und gibt dieses Zurück.

#define PAR_EVEN 0x00
#define PAR_ODD  0x01

uint8_t pMode;

pMode = PAR_EVEN;    // Parity Modus muss vorinitialisiert werden

uint8_t calcParity(uint8_t dataByte) {
  uint8_t parity;

      // Ermitteln ob die Anzahl der Einsen gerade oder ungerade ist
  parity = (dataByte >> 7);
  for (int i=6; i >= 0; i--) {
    parity = ((parity & 0b00000001) ^ ((dataByte >> i) & 0b00000001));
  }

      // Party Modus berücksichtigen
  if (pMode == PAR_EVEN) {
    return (parity ^ 0b00000000);
  } else if (pMode == PAR_ODD) {
        return (parity ^ 0b00000001);
  } else {
        return 0xFF;
      }
}

Rückgabewert:
0x00 -> Parity-Bit = 0
0x01 -> Parity-Bit = 1
0xFF -> Parity Mode wure nicht initialisiert

Der Code ist vielleicht nicht optimal, aber er funktioniert.
Bin für verbesserungsvorschläge immer offen.

Rev

Autor: Peter Dannegger (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Guckst Du parity.h:

parity_even_bit(val)


Peter

Autor: Rev (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hehe...äh, ich bin bei diesen Assembler Geschichten immer Misstrauisch
:P
Wahrscheinlich weil ich mich mit Assembler zu lange nicht mehr
beschäftigt habe...
Ich habs immer gerne in C ;)

Autor: Peter Dannegger (Gast)
Datum:
Angehängte Dateien:

Bewertung
0 lesenswert
nicht lesenswert
"Ich habs immer gerne in C ;)"

Kein Problem, anbei mal mein C-Code.


Peter

Autor: Gerd Laschinski (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hallo Peter,

ich persöhnlich finde das eleganter:

unsigned char parity( unsigned char val )
{
  val ^= val >> 4;
  val ^= val >> 2;
  val ^= val >> 1;
  val &= 0x01;
  return val;
}

Gruß
Gerd

Autor: Gerd Laschinski (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Oh, persönlich schreibt man ohne h ;-)

Gerd

Autor: pittbull (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
der ist schicker

// Returns 1 (ODD) or 0 (EVEN) parity
int parity (unsigned char x)
{
    x = x ^ x >> 4;
    x = x ^ x >> 2;
    x = x ^ x >> 1;
    return x & 1;
}

Autor: pittbull (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
ach shit, ich war zu lahm

Autor: Marcus (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
hi,

kann mir jemand den mathematischen beweis für die richtigkeit der
letzten, sehr eleganten lösung geben?

> unsigned char parity( unsigned char val )
>  {
>   val ^= val >> 4;
>   val ^= val >> 2;
>   val ^= val >> 1;
>   val &= 0x01;
>   return val;
> }

habs schon programmiert mit dem TI92 und es funzt immer einwandfrei,
aber ich bräuchte noch einen stichfesten (kurzen) mathematischen
beweis, dass es immer gilt.
da dies eine meiner "sehr großen stärken" ist, kann mir vllt. ja
jemand einen anstoß geben oder kurz den beweis erbringen?!?

danke euch!

Autor: pittbull_nt@yahoo.com (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
die parity von 2 bits wird mit einer exor-verknüpfung erzeugt:
-> p(a,b) = xor(a,b)
die parity von 4 bits kann in zwei 2-bit parities zerlegt werden also:
-> p(a,b,c,d) = xor (p(a,b), p(c,d))
oder auch:
-> p(a,b,c,d) = xor(xor(a,b), xor(c,d))
die parity von ungeradzahligen bitmustern berechnet sich z.b so:
-> p(a,b,c) = p(a,b) xor c
a,b und c können dabei beliebig vertauscht werden.

bei der funktion geht nun folgendes ab:
1.schritt: b ^= b>>1;
bildung der parities von bit(7,6), bit(5,4), bit(3,2) und bit(1,0).
die ergebnisse landen in den bits 6,4,2,0.
2. schritt: b^= b>> 2;
bildung der parities von bit(6,4) und bit(2,0).
die ergebnisse landen in den bits 4 und 0.
3. schritt: b^= b>>4;
bildung der parity von bit 4 und 0.
das endergebnis (gesamt-parity) ist in bit 0.

Autor: Marcus (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
danke, leider habe ich aber noch probleme damit:

beispiel anhand von 1110 1010

1. schritt, 4 nach rechts shiften:
=> 0000 1110   dann xor mit original daten 1110 1010
=> 1110 0100

hier passt doch schon die aussage "bildung der parities von bit(7,6)
[...]. die ergebnisse landen in den bits 6 [...]." nicht, oder sehe
ich da was falsch?

bin für jede hilfe dankbar.

... ahhh... moment... bei deiner erklärung sind die schritte
vertauscht. du fängst mit >>1 an...

... zettelrausholundausprobier

Autor: Marcus (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
zettelräuselknatterkram

das geht auch in umgekehrter reinfolge, kann das sein? also erst >> 1
dann >> 2 und dann >> 4

Autor: pittbull_nt@yahoo.com (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
ja, das geht auch andersrum. wichtig ist nur, dass die ergebnisse der
vorherigen xors solange ge-xor'd werden, bis nur ein bit übrig bleibt.

Autor: Ralf (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Ich bin auch gerade an der Parityberechnung.
Jedoch habe ich nur 15bit, die ich prüfen muss. Lässt sich hier auch 
irgendwie ein Algorithmus finden.
Oder kann ich irgendwie das auf 16bit erweitern und dann jeweils das 
high- und lowbyte prüfen?

Autor: A. K. (prx)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Ralf schrieb:

> Jedoch habe ich nur 15bit, die ich prüfen muss. Lässt sich hier auch
> irgendwie ein Algorithmus finden.

Gleiches Prinzip wie eben für 8 Bits, nur ein Schritt mehr:
unsigned parity16bit ( unsigned val )
{
  val ^= val >> 8;
  val ^= val >> 4;
  val ^= val >> 2;
  val ^= val >> 1;
  return val & 1;
}

Autor: Ralf (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Nur was mach ich dann mit dem 16. bit? Lass ich das dann einfach auf 0?

Autor: A. K. (prx)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Genau.

Für 8-Bit Prozessoren lässt sich die Routine natürlich noch bissel 
optimieren, weil nur die erste Operation in voller Breite erfolgen muss.

Autor: Johann L. (gjlayde) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Falls man GCC verwendet, so gibt es da __builtin_parity (x) zur 
Berechnung des Even-Parity.

Und für alle AVR Assembler-Freunde:
avr-gcc 4.7 verwendet z.B. folgende Sequenz für r24 = parity (r24)
    mov  __tmp_reg__, r24
    swap __tmp_reg__
    eor  r24, __tmp_reg__
    subi r24, -4
    andi r24, -5
    subi r24, -6
    sbrc r24, 3
    inc  r24
    andi r24, 1

Autor: ext (Gast)
Datum:
Angehängte Dateien:

Bewertung
0 lesenswert
nicht lesenswert
Die oben genannte Routine bildet das Paritybit als das XOR über alle 8 
Stellen mit nur einem Register. Zum Schluss steht das XOR über die 
Stellen B,C,D,F,G,H in Bit 3, das XOR über A und E in Bit 0. Den Rest 
erledigt eine Fallunterscheidung.

(siehe Anhang)

Autor: Johann L. (gjlayde) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
ext schrieb:
> Die oben genannte Routine bildet das Paritybit als das XOR über alle 8
> Stellen mit nur einem Register. Zum Schluss steht das XOR über die
> Stellen B,C,D,F,G,H in Bit 3, das XOR über A und E in Bit 0. Den Rest
> erledigt eine Fallunterscheidung.

ähhh... ist das ein Korrektsheitsbeweis der Sequenz die
ich in obigem Beitrag schrieb:

Ich bin beeindruckt.

Antwort schreiben

Die Angabe einer E-Mail-Adresse ist freiwillig. Wenn Sie automatisch per E-Mail über Antworten auf Ihren Beitrag informiert werden möchten, melden Sie sich bitte an.

Wichtige Regeln - erst lesen, dann posten!

  • Groß- und Kleinschreibung verwenden
  • Längeren Sourcecode nicht im Text einfügen, sondern als Dateianhang

Formatierung (mehr Informationen...)

  • [c]C-Code[/c]
  • [avrasm]AVR-Assembler-Code[/avrasm]
  • [code]Code in anderen Sprachen, ASCII-Zeichnungen[/code]
  • [math]Formel in LaTeX-Syntax[/math]
  • [[Titel]] - Link zu Artikel
  • Verweis auf anderen Beitrag einfügen: Rechtsklick auf Beitragstitel,
    "Adresse kopieren", und in den Text einfügen




Bild automatisch verkleinern, falls nötig
Bitte das JPG-Format nur für Fotos und Scans verwenden!
Zeichnungen und Screenshots im PNG- oder
GIF-Format hochladen. Siehe Bildformate.
Hinweis: der ursprüngliche Beitrag ist mehr als 6 Monate alt.
Bitte hier nur auf die ursprüngliche Frage antworten,
für neue Fragen einen neuen Beitrag erstellen.

Mit dem Abschicken bestätigst du, die Nutzungsbedingungen anzuerkennen.