Serwis Edukacyjny
w I-LO w Tarnowie
obrazek

Materiały dla uczniów liceum

  Wyjście       Spis treści       Wstecz       Dalej  

Autor artykułu: mgr Jerzy Wałaszek

©2020 mgr Jerzy Wałaszek
I LO w Tarnowie

Bity w elektronice

Generator bitu parzystości

SPIS TREŚCI
Podrozdziały

Opis

Bit parzystości umożliwia pewną ochronę transmisji danych przed błędami. Dokładnie opisaliśmy jego zastosowanie w rozdziale o kodach EDC. W tym projekcie naszym zadaniem jest stworzenie sieci logicznej, która generuje bit parzystości dla 8 bitów danych informacyjnych. Sieć będzie posiadała 8 wejść, na które podajemy kolejne bity informacyjne, oraz jedno wyjście, na którym pojawia się bit parzystości. Poniżej przedstawiamy schemat blokowy takiej sieci:

obrazek

Na początek:  podrozdziału   strony 

Określenie funkcji logicznych

Stworzenie układu cyfrowego generującego bit parzystości na pierwszy rzut oka wydaje się trudne. W rzeczywistości tak nie jest. Przypomnijmy sobie funkcję różnicy symetrycznej realizowaną przez bramkę EX-OR (układ TTL - SN7486, CMOS - CD4070) :

Bramka EX-OR
Symulator
A B y
0 0 0
0 1 1
1 0 1
1 1 0

Na wyjściu otrzymujemy 1, jeśli na wejściu bramki jest nieparzysta liczba jedynek. Własność tą wykorzystamy w układzie generacji bitu parzystości. Nad każdą parą bitów w zbiorze wejściowym:

{ b1, b2, b3, b4, b5, b6, b7, b8 }

wykonujemy operację różnicy symetrycznej:

w1 = b1 ⊕ b2
w2 = b3 ⊕ b4
w3 = b5 ⊕ b6
w4 = b7 ⊕ b8

W wyniku otrzymujemy nowy zbiór 4-elementowy:

{ w1, w2, w3, w4 }

Jeśli w zbiorze { b1, b2, b3, b4, b5, b6, b7, b8 } była parzysta liczba jedynek, to w zbiorze { w1, w2, w3, w4 } również musi ich być ilość parzysta. Ta sama własność jest również spełniona dla nieparzystości. Po prostu operacja różnicy symetrycznej zachowuje parzystość i nieparzystość. Uzasadnienie jest bardzo proste:

Parzystość:

Zakładamy, iż zbiór { b1, b2, b3, b4, b5, b6, b7, b8 } zawiera parzystą liczbę jedynek. Jeśli w parze kolejnych bitów występują dwie jedynki lub dwa zera, to różnica symetryczna da nam w wyniku 0, które jest zawsze parzyste. Jeśli w jednej z par bity są różne, to dostaniemy w wyniku 1, lecz z uwagi na parzystość zbioru wejściowego, w innej parze również muszą być dwa różne bity. Zatem dostaniemy dwie jedynki, a to jest ilość parzysta. W wyniku zawsze dostaniemy parzystą ilość bitów 1. Innych możliwości nie ma.

Nieparzystość:

Zakładamy, iż zbiór { b1, b2, b3, b4, b5, b6, b7, b8 } zawiera nieparzystą liczbę jedynek. Wynika z tego, iż ilość par kolejnych bitów, które różnią się od siebie jest liczbą nieparzystą. Każda taka para zostanie zamieniona przez różnicę symetryczną na 1. Zatem w zbiorze wynikowym ilość jedynek będzie nieparzysta. Innych możliwości nie ma.

Udowodniliśmy, iż zbiór wynikowy { w1, w2, w3, w4 } zachowuje parzystość/nieparzystość zbioru wejściowego { b1, b2, b3, b4, b5, b6, b7, b8 }, ale liczba bitów jest dwukrotnie mniejsza. Nad zbiorem wynikowym znów wykonujemy operację różnicy symetrycznej:

x1 = w1 ⊕ w2
x2 = w3 ⊕ w4

Otrzymujemy kolejny zbiór wynikowy { x1, x2 }, który zachowuje parzystość/nieparzystość zbioru { w1, w2, w3, w4 }, a zatem także parzystość/nieparzystość zbioru wejściowego { b1, b2, b3, b4, b5, b6, b7, b8 }. Nad bitami x1 i x2 znów wykonujemy operację różnicy symetrycznej:

y = x1 ⊕ x2

Wynik y jest równy 1, jeśli zbiór wejściowy zawierał nieparzystą ilość bitów 1, a 0, gdy liczba bitów 1 była parzysta. Zatem y jest poszukiwanym bitem parzystości. Aby otrzymać pełną funkcję zastąpmy kolejne symbole x i w wykonanymi operacjami:

y = x1 ⊕ x2
y = (  w1 ⊕ w2 ) ⊕ ( w3 ⊕ w4 )
y = (( b1 ⊕ b2 ) ⊕ ( b3 ⊕ b4 )) ⊕ (( b5 ⊕ b6 ) ⊕ ( b7 ⊕ b8 ))

Otrzymaliśmy wzór funkcji generującej bit parzystości:

Gdybyśmy potrzebowali funkcji generującej bit nieparzystości, to wystarczy zanegować naszą funkcję:

Na początek:  podrozdziału   strony 

Budowa sieci logicznej

Cała sieć logiczna będzie zbudowana z bramek EX-OR. Zaczynamy od sygnałów wejściowych:

Teraz realizujemy kolejne człony wzoru funkcji za pomocą bramek EX-OR:





Teraz realizujemy drugi poziom:



I ostatni, trzeci poziom:


Sieć logiczna jest gotowa. Ponieważ bramki pracują kaskadowo, to stan wyjściowy ustali się po około trzykrotnym czasie propagacji dla pojedynczej bramki EX-OR.

Na początek:  podrozdziału   strony 

Symulacja sieci w języku C++

Numerujemy bramki zgodnie z kolejnością przetwarzania sygnałów:

Określamy sieć połączeń:

YB1 = EXOR(b1,b2)
YB2 = EXOR(b3,b4)
YB3 = EXOR(b5,b6)
YB4 = EXOR(b7,b8)
YB5 = EXOR(YB1,YB2)
YB6 = EXOR(YB3,YB4)
YB7 = EXOR(YB5,YB6)
y = YB7

8 bitów danych daje 2 8 = 256 kombinacji stanów wejściowych. Nasz program symulacyjny tworzy wszystkie 256 stanów wejść b1...b8, po czym wyznacza bit parzystości y na podstawie sieci połączeń. Na koniec program zlicza liczbę bitów 1 w słowie wyjściowym b1...b8 plus bit parzystości. Jeśli liczba bitów jest parzysta, to wyświetla napis OK. Napis ?? obok słowa wyjściowego oznacza błędne działanie sieci.
C++
// Symulacja sieci logicznej
// generatora bitu parzystości
// (C)2020 mgr Jerzy Wałaszek
// I LO w Tarnowie

#include <iostream>

using namespace std;

// Funkcje bramek

int EXOR(int a, int b)
{
    return (a ^ b);
}

int main( )
{
  // Stany wejściowe oraz stan wyjściowy
  int b1,b2,b3,b4,b5,b6,b7,b8,y;

  // Stany wyjściowe bramek
  int YB1,YB2,YB3,YB4,YB5,YB6,YB7;

  // Licznik bitów o stanie 1
  int cnt1;

  // Licznik słów
  int wc = 0;
  // Generujemy kolejne stany wejściowe

  for(b8 = 0; b8 < 2; b8++)
    for(b7 = 0; b7 < 2; b7++)
      for(b6 = 0; b6 < 2; b6++)
        for(b5 = 0; b5 < 2; b5++)
          for(b4 = 0; b4 < 2; b4++)
            for(b3 = 0; b3 < 2; b3++)
              for(b2 = 0; b2 < 2; b2++)
                for(b1 = 0; b1 < 2; b1++)
                {
                  // Symulacja sieci

                  YB1 = EXOR(b1,b2);
                  YB2 = EXOR(b3,b4);
                  YB3 = EXOR(b5,b6);
                  YB4 = EXOR(b7,b8);
                  YB5 = EXOR(YB1,YB2);
                  YB6 = EXOR(YB3,YB4);
                  YB7 = EXOR(YB5,YB6);

                  // Stan wyjściowy

                  y = YB7;

                  // Obliczamy ilość bitów 1

                  cnt1 = y +
                         b1 + b2 + b3 + b4 +
                         b5 + b6 + b7 + b8;

                  // Wyświetlamy wyniki

                  cout << b8 << b7 << b6 << b5
                       << b4 << b3 << b2 << b1
                       << "|" << y << " - ";
                  if(cnt1 % 2) cout << "??";
                  else         cout << "OK";
                  cout << "   ";
                  wc++;
                  if(wc == 4)
                  {
                      wc = 0;
                      cout << endl;
                  }
                }
  cout << endl;

  return 0;
}
Wynik:
00000000|0 - OK   00000001|1 - OK   00000010|1 - OK   00000011|0 - OK
00000100|1 - OK   00000101|0 - OK   00000110|0 - OK   00000111|1 - OK
00001000|1 - OK   00001001|0 - OK   00001010|0 - OK   00001011|1 - OK
00001100|0 - OK   00001101|1 - OK   00001110|1 - OK   00001111|0 - OK
00010000|1 - OK   00010001|0 - OK   00010010|0 - OK   00010011|1 - OK
00010100|0 - OK   00010101|1 - OK   00010110|1 - OK   00010111|0 - OK
00011000|0 - OK   00011001|1 - OK   00011010|1 - OK   00011011|0 - OK
00011100|1 - OK   00011101|0 - OK   00011110|0 - OK   00011111|1 - OK
00100000|1 - OK   00100001|0 - OK   00100010|0 - OK   00100011|1 - OK
00100100|0 - OK   00100101|1 - OK   00100110|1 - OK   00100111|0 - OK
00101000|0 - OK   00101001|1 - OK   00101010|1 - OK   00101011|0 - OK
00101100|1 - OK   00101101|0 - OK   00101110|0 - OK   00101111|1 - OK
00110000|0 - OK   00110001|1 - OK   00110010|1 - OK   00110011|0 - OK
00110100|1 - OK   00110101|0 - OK   00110110|0 - OK   00110111|1 - OK
00111000|1 - OK   00111001|0 - OK   00111010|0 - OK   00111011|1 - OK
00111100|0 - OK   00111101|1 - OK   00111110|1 - OK   00111111|0 - OK
01000000|1 - OK   01000001|0 - OK   01000010|0 - OK   01000011|1 - OK
01000100|0 - OK   01000101|1 - OK   01000110|1 - OK   01000111|0 - OK
01001000|0 - OK   01001001|1 - OK   01001010|1 - OK   01001011|0 - OK
01001100|1 - OK   01001101|0 - OK   01001110|0 - OK   01001111|1 - OK
01010000|0 - OK   01010001|1 - OK   01010010|1 - OK   01010011|0 - OK
01010100|1 - OK   01010101|0 - OK   01010110|0 - OK   01010111|1 - OK
01011000|1 - OK   01011001|0 - OK   01011010|0 - OK   01011011|1 - OK
01011100|0 - OK   01011101|1 - OK   01011110|1 - OK   01011111|0 - OK
01100000|0 - OK   01100001|1 - OK   01100010|1 - OK   01100011|0 - OK
01100100|1 - OK   01100101|0 - OK   01100110|0 - OK   01100111|1 - OK
01101000|1 - OK   01101001|0 - OK   01101010|0 - OK   01101011|1 - OK
01101100|0 - OK   01101101|1 - OK   01101110|1 - OK   01101111|0 - OK
01110000|1 - OK   01110001|0 - OK   01110010|0 - OK   01110011|1 - OK
01110100|0 - OK   01110101|1 - OK   01110110|1 - OK   01110111|0 - OK
01111000|0 - OK   01111001|1 - OK   01111010|1 - OK   01111011|0 - OK
01111100|1 - OK   01111101|0 - OK   01111110|0 - OK   01111111|1 - OK
10000000|1 - OK   10000001|0 - OK   10000010|0 - OK   10000011|1 - OK
10000100|0 - OK   10000101|1 - OK   10000110|1 - OK   10000111|0 - OK
10001000|0 - OK   10001001|1 - OK   10001010|1 - OK   10001011|0 - OK
10001100|1 - OK   10001101|0 - OK   10001110|0 - OK   10001111|1 - OK
10010000|0 - OK   10010001|1 - OK   10010010|1 - OK   10010011|0 - OK
10010100|1 - OK   10010101|0 - OK   10010110|0 - OK   10010111|1 - OK
10011000|1 - OK   10011001|0 - OK   10011010|0 - OK   10011011|1 - OK
10011100|0 - OK   10011101|1 - OK   10011110|1 - OK   10011111|0 - OK
10100000|0 - OK   10100001|1 - OK   10100010|1 - OK   10100011|0 - OK
10100100|1 - OK   10100101|0 - OK   10100110|0 - OK   10100111|1 - OK
10101000|1 - OK   10101001|0 - OK   10101010|0 - OK   10101011|1 - OK
10101100|0 - OK   10101101|1 - OK   10101110|1 - OK   10101111|0 - OK
10110000|1 - OK   10110001|0 - OK   10110010|0 - OK   10110011|1 - OK
10110100|0 - OK   10110101|1 - OK   10110110|1 - OK   10110111|0 - OK
10111000|0 - OK   10111001|1 - OK   10111010|1 - OK   10111011|0 - OK
10111100|1 - OK   10111101|0 - OK   10111110|0 - OK   10111111|1 - OK
11000000|0 - OK   11000001|1 - OK   11000010|1 - OK   11000011|0 - OK
11000100|1 - OK   11000101|0 - OK   11000110|0 - OK   11000111|1 - OK
11001000|1 - OK   11001001|0 - OK   11001010|0 - OK   11001011|1 - OK
11001100|0 - OK   11001101|1 - OK   11001110|1 - OK   11001111|0 - OK
11010000|1 - OK   11010001|0 - OK   11010010|0 - OK   11010011|1 - OK
11010100|0 - OK   11010101|1 - OK   11010110|1 - OK   11010111|0 - OK
11011000|0 - OK   11011001|1 - OK   11011010|1 - OK   11011011|0 - OK
11011100|1 - OK   11011101|0 - OK   11011110|0 - OK   11011111|1 - OK
11100000|1 - OK   11100001|0 - OK   11100010|0 - OK   11100011|1 - OK
11100100|0 - OK   11100101|1 - OK   11100110|1 - OK   11100111|0 - OK
11101000|0 - OK   11101001|1 - OK   11101010|1 - OK   11101011|0 - OK
11101100|1 - OK   11101101|0 - OK   11101110|0 - OK   11101111|1 - OK
11110000|0 - OK   11110001|1 - OK   11110010|1 - OK   11110011|0 - OK
11110100|1 - OK   11110101|0 - OK   11110110|0 - OK   11110111|1 - OK
11111000|1 - OK   11111001|0 - OK   11111010|0 - OK   11111011|1 - OK
11111100|0 - OK   11111101|1 - OK   11111110|1 - OK   11111111|0 - OK

Na początek:  podrozdziału   strony 

Symulacja interaktywna

Bity danych ustawiasz za pomocą prostokątnych przycisków. Kliknięcie przycisku myszką zmienia jego stan na przeciwny. Kolor czarny oznacza 0, kolor czerwony oznacza 1. Stan bitu parzystości y odczytujesz z okrągłego pola.

Symulator
Na początek:  podrozdziału   strony 

Spis elementów

Obciążenia wejść:

b1...b8 = 1
SN7486 × 2
 obrazek

Przemysł elektroniczny produkuje gotowe układy zawierające generator bitu parzystości/nieparzystości, np. SN74180.

Na początek:  podrozdziału   strony 

Zespół Przedmiotowy
Chemii-Fizyki-Informatyki

w I Liceum Ogólnokształcącym
im. Kazimierza Brodzińskiego
w Tarnowie
ul. Piłsudskiego 4
©2020 mgr Jerzy Wałaszek

Materiały tylko do użytku dydaktycznego. Ich kopiowanie i powielanie jest dozwolone
pod warunkiem podania źródła oraz niepobierania za to pieniędzy.

Pytania proszę przesyłać na adres email: i-lo@eduinf.waw.pl

Serwis wykorzystuje pliki cookies. Jeśli nie chcesz ich otrzymywać, zablokuj je w swojej przeglądarce.
Informacje dodatkowe.