Even/Odd Parity berechnen

Gast #187591
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
Gast #187593
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 ;)
Gast #187595
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
Gast #187597
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;
}
Gast #187599
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!
Gast #187600
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.
Gast #187601
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
Gast #187603
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.
Gast #2351263
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?
#2351272
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:
1
unsigned parity16bit ( unsigned val )
2
{
3
  val ^= val >> 8;
4
  val ^= val >> 4;
5
  val ^= val >> 2;
6
  val ^= val >> 1;
7
  return val & 1;
8
}
Persönliche Seite #2356513
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)
1
    mov  __tmp_reg__, r24
2
    swap __tmp_reg__
3
    eor  r24, __tmp_reg__
4
    subi r24, -4
5
    andi r24, -5
6
    subi r24, -6
7
    sbrc r24, 3
8
    inc  r24
9
    andi r24, 1
Gast #2859897
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)
Angehängte Dateien:
Persönliche Seite #2866120
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

Eine eigene Frage? Dieser Thread ist über 21 Jahre alt. Stell sie in einem eigenen Thread – dort lesen mehr Leute mit, und sie wird öfter und schneller beantwortet.

Neuen Thread starten

Eine Lösung, Ergänzung oder Rückmeldung zu diesem Thread? Dann antworte hier.

Formatierung
  • [c]C-Code[/c]
  • [code]Code in anderen Sprachen, ASCII-Zeichnungen[/code]
  • [math]Formel in LaTeX-Syntax[/math]
  • [[Titel]] – Link zu einem Artikel
  • Verweis auf einen anderen Beitrag: Rechtsklick auf dessen Beitrags-ID (#8078628), „Adresse kopieren“, in den Text einfügen

Mehr zur Formatierung

Längeren Sourcecode als Anhang, nicht in den Text. JPG nur für Fotos und Scans; Zeichnungen und Screenshots als PNG oder GIF. Siehe Bildformate.

Schon registriert? Anmelden

Wird nicht angezeigt. Wir schicken dir einen Link; sobald du damit bestätigst, erscheint dein Beitrag.

Mit dem Abschicken legst du einen kostenlosen Account an und erkennst die Nutzungsbedingungen und die Datenschutzerklärung an.