Bit parnosti
7 bitova podataka |
(računati od 1 bita) | 8 bitova uključujući parnost | |
---|---|---|---|
parno | neparno | ||
0000000 | 0 | 00000000 | 00000001 |
1010001 | 3 | 10100011 | 10100010 |
1101001 | 4 | 11010010 | 11010011 |
1111111 | 7 | 11111111 | 11111110 |
Bit parnosti, ili bit provere, je bit koji je dodat na kraj stringa binarnog koda koji pokazuje da li je broj bitova u stringu sa vrednošću jedan paran ili neparan. Parnost bita se koristi kao najjednostavniji oblik koda za detekciju greške.
Postoje dve varijante parnosti bitova: parna parnost bitova i neparna parnost bitova. U slučaju parne parnosti, parnost bita se postavlja na 1 ako je broj jedinica u datom skupu bitova (ne uključujući bit parnosti) neparan, čineći brojanje jedinica u celom skupu bita (uključujući i parnost bita ) parnim. Ukoliko je paran broj jedinica u datom skupu bitova, postavlja se na 0. Kada koristite neparanu parnost, bit parnosti se postavlja na 1 je broj jedinica u datom skupu (ne uključujući bit parnosti) paran, čineći broj jedinica u celom skupu bitova (uključujući i bit parnosti) neparnim. Kada je broj postavljenih bitova neparan, onda neparni bit parnosti se postavlja na 0.
Parna parnost je poseban slučaj CRC-a, gde je 1-bit CRC-a generisan polinomom x+1.
Ako je bit parnosti prisutan, ali se ne koristi, može se odnositi na oznaku parnosti (kada je bit parnosti uvek 1) ili na prostor parnosti (bit je uvek 0).
Parnost
[uredi | uredi izvor]U matematici, parnost se odnosi na parnost ili neparnost celog broja, koji za binarni broj određen preko bita najnižeg prioriteta. U telekomunikacijama i računarstvu, parnosti odnosi na parnost ili neparnost broja bitova sa jednim vrednošću u okviru datog skupa bitova, pa je na taj način određena vrednost svih bitova. Može se izračunati preko EKSILI zbira bitova, dajući 0 za parnu parnost i 1 za neparnu parnost. Ovo svojstvo zavisi od svih bitova i menja vrednost ako bilo koji bit promene došušta njegovu upotrebu u šemama za detekciju grešaka.
Detekcija greške
[uredi | uredi izvor]Ako se neparan broj bitova (uključujući bit parnosti) emituje nepravilno, bit parnosti će biti netačan, što ukazuje da je do greške parnosti došlo u prenosu. Bit parnosti je jedino pogodan za otkrivanje grešaka; on ne može ispraviti bilo kakve greške, jer ne postoji način da se utvrdi koji bit je tačno oštećen. Podaci moraju biti u potpunosti odbačeni, a ponovno emitovani od oštećenja. Na bučnom prenosnom medijumu, uspešan prenos može da potraje dugo vremena, ili čak da se nikad ne izvrši. Međutim, parnost ima tu prednost što koristi samo jedan bit i da bi generisao koristi samo brojeve EKSILI kapije. Pogledajte Hamingov kod za primer koda za korekciju greške.
Bit parnosti povremeno proverava prenos ASCII karaktera, koji imaju 7 bitova, ostavljajući 8. bit kao bit parnosti.
Na primer, bit parnosti može se izračunati na sledeći način, pod pretpostavkom da šaljemo jednostavnu 4-bitnu vrednost 1001 sa bitom parnosti sa desne strane, i sa ^ označavamo EKSILI kapiju:
Tip bita parnosti | Uspešni scenario prenosa |
---|---|
Parna parnost |
A želi da prenese: 1001 A računa vrednost bita parnosti: 1^0^0^1 = 0 A dodaje bit parnosti i šalje: 10010 B prihvata: 10010 B izračunava parnost: 1^0^0^1^0 = 0 B prijavljuje korektni prenos posle posmatranog očekivanog parnog rezultata. |
Neparna parnost |
A želi da prenese: 1001 A računa vrednost bita parnosti: ~(1^0^0^1) = 1 A dodaje bit parnosti i šalje: 10011 B prihvata: 10011 B izračunava parnost: 1^0^0^1^1 = 1 B prijavljuje korektni prenos posle posmatranog očekivanog neparnog rezultata. |
Ovaj mehanizam omogućava otkrivanje greške jednog bita, jer ako neki bit zameni vrednost u liniji, tu će biti netačan broj jedinica u dobijenom podatku. U prethodna dva primera, V izračunava bit parnosti i proverava da li odgovara bitu parnosti u primljenoj vrednosti, što ukazuje da nema nijedne greške bita. Razmotrite sledeći primer sa greškom prenosa u drugom bitu:
Tip bita parnosti | Scenario greške prenosa |
---|---|
Parna parnost
Greška u drugom bitu |
A želi da prenese: 1001
A računa vrednost bita parnosti: 1^0^0^1 = 0 A dodaje bit parnosti i šalje: 10010 ... GREŠKA PRENOSA... B prihvata: 11010 B izračunava parnost: 1^1^0^1^0 = 1 B prijavljuje netačan prenos posle posmatranog očekivanog neparnog rezultata. |
Neparna parnost
Greška u parnosti bita |
A želi da prenese: 1001
A računa vrednost bita parnosti: 1^0^0^1 = 0 A šalje: 10010 ... GREŠKA PRENOSA... B prihvata: 10011 B izračunava parnost: 1^0^0^1^1 = 1 B prijavljuje netačan prenos posle posmatranog očekivanog neparnog rezultata. |
Postoji ograničenje na šemi parnosti. Bit parnosti garantuje samo da detektuje neparan broj grešaka bitova. Ako parani broj bitova ima grešaka, bit parnosti beleži tačan broj jedinica, iako su podaci oštećeni. (Videti takođe detekciju i korekcju greške.) Razmotrimo isti primer kao i ranije sa parnim brojem oštećenih bitova:
Tip bita parnosti | Scenario neuspelog prenosa |
---|---|
Parna parnost
Dva oštećena bita |
A želi da prenese: 1001
A računa vrednost bita parnosti: 1^0^0^1 = 0 A šalje: 10010 ... GREŠKA PRENOSA... B prihvata: 11011 B izračunava parnost: 1^1^0^1^1 = 0 B prijavljuje tačan prenos iako je zapravo netačan. |
B posmatra parnu parnost, kao što je očekivano, ne uspeva da uhvati grešku dva bita
Upotreba
[uredi | uredi izvor]Zbog svoje jednostavnosti, parnost se koristi u mnogim hardverskim aplikacijama gde se, u slučaju poteškoća, neka operacija može ponavljati, ili gde je jednostavno otkrivanje greške korisno. Na primer, SCSI i PCI magistrale koriste parnost da bi detektovali prenosne greške, a mnoge mikroprocesorske keš instrukcije uključuju zaštitu parnosti. Zato što instrukcija keš podataka je samo kopija glavne memorije, ona može biti zanemarena i ponovo preuzeta ukoliko se pokaže da je bila oštećena.
U serijskom prenosu podataka, zajednički format je 7 bita, parni bit, i jedan ili dva zaustavljajuća bita. Ovaj format uredno smešta sve 7-bitne ASCII karaktere u pogodne 8-bitne bajtove. Ostali mogući formati; 8 bitova podataka, plus bit parnosti mogu preneti sve 8-bitne vrednosti bajta.
U kontekstu serijskih komunikacija, parnost se obično generiše i proverava od strane interfejsa hardvera (npr. UART) i, na prijemu, rezultat postaje dostupan procesoru (i tako, na primer, Operativni sistem) pomoću statusa bita u registru hardvera u interfejsu hardvera. Oporavak od greške se obično radi tako što se ponovo pošalju podaci, pojedinosti kojima obično barata softver (npr. operativni sistem U/I rutina).
RAID
[uredi | uredi izvor]Parnost podataka se koristi pri određenim RAID nivoima da bi se postigla redundantnost. Ako disk u nizu ne uspe, preostali podaci na drugim diskovima mogu se kombinovati sa parnošću podataka (koristeći Bulovu EKSILI funkciju) da rekonstruiše podatke koji nedostaju.
Na primer, pretpostavimo da dva diska od tri diska RAID 5 niza sadrže sledeće podatke:
Disk 1: 01101101
Disk 2: 11010100
Da biste izračunali parnost podataka za dva diska, EKSILI se vrši na njihovom podacima:
01101101
EKSILI 11010100
_____________
10111001
Dobijena parnost podatka, 10111001, je sačuvana na Disku 3.
Ukoliko bilo koji od tri diska otkaže, sadržaj propalog diska može se rekonstruisati na kopiranom disku izlaganjem podataka iz ostalih diskova istim EKSILI operacijama. Ako disk 2 otkaže, njegovi podaci mogu biti obnovljeni korišćenjem sadržaja EKSILI rezultata dva preostala diska, disk 1 i disk 3:
Disk 1: 01101101
Disk 3: 10111001
kao što sledi:
10111001
EKSILI 01101101
_____________
11010100
Rezultat EKSILI kalkulacije daje sadržaj Diska 2. 11010100 je sačuvano na Disku 2, koji je potpuno popravljen niz. Ovaj isti EKSILI koncept se koristi slično i u većim nizovima, koristeći bilo koji broj diskova. U slučaju RAID-a 3, niza od 12 diskova, 11 diskova učestvuju u EKSILI kalkulacijama prikazanim gore i dobijaju vrednost koja se potom čuva na namenskom disku parnosti.
Istorija
[uredi | uredi izvor]"Staza parnosti" je bila prisutna na prvoj magnetnoj traci za skladištenje podataka, 1951. godine. Parnost u ovom obliku, primenjena preko više paralelnih signala, je poznata kao uzdužna redundantna provera. Ovo se može kombinovati sa parnosti obračunatoj preko više bitova poslatih na jedan signal, uzdužne redundantne provere. U paralelnoj magistrali, postoji jedna uzdužna redundantna provera bita po paralelnom signalu.
Parnost se takođe koristila na nekim papirnim trakama (punched tape)koje su služile za unos podataka (kojima su prethodile magnetne trake). Na prodatim sistemima Britanske kompanije ICL (ranije ICT) 1 in-wide (25 mm) papir traka imala je 8 pozicija rupa preko nje, 8. je bila za parnost. Ostalih 7 pozicija su korišćene za podatke, npr, 7-bitni ASCII. Osma pozicija je imala izbušenu rupu u zavisnosti od broja izbušenih rupa za podatke.
Nasuprot mišljenju, Simor Kreja, prvog dizajnera superračunara, koji nije poštovao dizajniranje parnosti. To je pokazao na sirmoašnom dizajnu - ako dizajnirte svoje putanje prenosa da budu pouzdane, onda ne morate da gubite resurse na parnosti. Njegov čuveni citat na ovo (oko 1963.) bio je "Parnost je za poljoprivrednike" (posle upotrebe termina "parnosti" u New Deal-u). Nakon što je kasnije uknjučio bit parnosti na CDC 7600, Krej je navodno rekao: "Shvatio sam da dosta poljoprivrednika kupuje računare".[1]
Vidi još
[uredi | uredi izvor]Reference
[uredi | uredi izvor]- ^ "Quotable Quotes by Seymour R. Cray" "The following UNVERIFIED quotes have been widely attributed to Seymour R. Cray."