Бит парности

Из Википедије, слободне енциклопедије
7 битова податакаа
(рачунати од 1 бита) 8 битова укључујући парност
парно непарно
0000000 0 00000000 00000001
1010001 3 10100011 10100010
1101001 4 11010010 11010011
1111111 7 11111111 11111110

Бит парности, или бит провере, је бит који је додат на крај стринга бинарног кода који показује да ли је број битова у стрингу са вредношћу један паран или непаран. Парност бита се користи као најједноставнији облик кода за детекцију грешке.

Постоје две варијанте парности битова: парна парност битова и непарна парност битова. У случају парне парности, парност бита се поставља на 1 ако је број јединица у датом скупу битова (не укључујући бит парности) непаран, чинећи бројање јединица у целом скупу бита (укључујући и парност бита ) парним. Уколико је паран број јединица у датом скупу битова, поставља се на 0. Када користите непарану парност, бит парности се поставља на 1 је број јединица у датом скупу (не укључујући бит парности) паран, чинећи број јединица у целом скупу битова (укључујући и бит парности) непарним. Када је број постављених битова непаран, онда непарни бит парности се поставља на 0.

Парна парност је посебан случај CRC-а, где је 1-бит CRC-а генерисан полиномом x+1.

Ако је бит парности присутан, али се не користи, може се односити на ознаку парности (када је бит парности увек 1) или на простор парности (бит је увек 0).

Парност[уреди]

У математици, парност се односи на парност или непарност целог броја, који за бинарни број одређен преко бита најнижег приоритета. У телекомуникацијама и рачунарству, парности односи на парност или непарност броја битова са једним вредношћу у оквиру датог скупа битова, па је на тај начин одређена вредност свих битова. Може се израчунати преко ЕКСИЛИ збира битова, дајући 0 за парну парност и 1 за непарну парност. Ово својство зависи од свих битова и мења вредност ако било који бит промене дошушта његову употребу у шемама за детекцију грешака.

Детекција грешке[уреди]

Ако се непаран број битова (укључујући бит парности) емитује неправилно, бит парности ће бити нетачан, што указује да је до грешке парности дошло у преносу. Бит парности је једино погодан за откривање грешака; он не може исправити било какве грешке, јер не постоји начин да се утврди који бит је тачно оштећен. Подаци морају бити у потпуности одбачени, а поновно емитовани од оштећења. На бучном преносном медијуму, успешан пренос може да потраје дуго времена, или чак да се никад не изврши. Међутим, парност има ту предност што користи само један бит и да би генерисао користи само бројеве ЕКСИЛИ капије. Погледајте Хамингов код за пример кода за корекцију грешке.

Бит парности повремено проверава пренос ASCII карактера, који имају 7 битова, остављајући 8. бит као бит парности.

На пример, бит парности може се израчунати на следећи начин, под претпоставком да шаљемо једноставну 4-битну вредност 1001 са битом парности са десне стране, и са ^ означавамо ЕКСИЛИ капију:

Тип бита парности Успешни сценарио преноса
Парна парност

A жели да пренесе: 1001

A рачуна вредност бита парности: 1^0^0^1 = 0

A додаје бит парности и шаље: 10010

B прихвата: 10010

B израчунава парност: 1^0^0^1^0 = 0

B пријављује коректни пренос после посматраног очекиваног парног резултата.

Непарна парност

A жели да пренесе: 1001

A рачуна вредност бита парности: ~(1^0^0^1) = 1

A додаје бит парности и шаље: 10011

B прихвата: 10011

B израчунава парност: 1^0^0^1^1 = 1

B пријављује коректни пренос после посматраног очекиваног непарног резултата.


Овај механизам омогућава откривање грешке једног бита, јер ако неки бит замени вредност у линији, ту ће бити нетачан број јединица у добијеном податку. У претходна два примера, В израчунава бит парности и проверава да ли одговара биту парности у примљеној вредности, што указује да нема ниједне грешке бита. Размотрите следећи пример са грешком преноса у другом биту:

Тип бита парности Сценарио грешке преноса
Парна парност

Грешка у другом биту

A жели да пренесе: 1001

A рачуна вредност бита парности: 1^0^0^1 = 0

A додаје бит парности и шаље: 10010

... ГРЕШКА ПРЕНОСА...

B прихвата: 11010

B израчунава парност: 1^1^0^1^0 = 1

B пријављује нетачан пренос после посматраног очекиваног непарног резултата.

Непарна парност

Грешка у парности бита

A жели да пренесе: 1001

A рачуна вредност бита парности: 1^0^0^1 = 0

A шаље: 10010

... ГРЕШКА ПРЕНОСА...

B прихвата: 10011

B израчунава парност: 1^0^0^1^1 = 1

B пријављује нетачан пренос после посматраног очекиваног непарног резултата.

Постоји ограничење на шеми парности. Бит парности гарантује само да детектује непаран број грешака битова. Ако парани број битова има грешака, бит парности бележи тачан број јединица, иако су подаци оштећени. (Видети такође детекцију и корекцју грешке.) Размотримо исти пример као и раније са парним бројем оштећених битова:

Тип бита парности Сценарио неуспелог преноса
Парна парност

Два оштећена бита

A жели да пренесе: 1001

A рачуна вредност бита парности: 1^0^0^1 = 0

A шаље: 10010

... ГРЕШКА ПРЕНОСА...

B прихвата: 11011

B израчунава парност: 1^1^0^1^1 = 0

B пријављује тачан пренос иако је заправо нетачан.

B посматра парну парност, као што је очекивано, не успева да ухвати грешку два бита

Употреба[уреди]

Због своје једноставности, парност се користи у многим хардверским апликацијама где се, у случају потешкоћа, нека операција може понављати, или где је једноставно откривање грешке корисно. На пример, SCSI и PCI магистрале користе парност да би детектовали преносне грешке, а многе микропроцесорске кеш инструкције укључују заштиту парности. Зато што инструкција кеш података је само копија главне меморије, она може бити занемарена и поново преузета уколико се покаже да је била оштећена.

У серијском преносу података, заједнички формат је 7 бита, парни бит, и један или два заустављајућа бита. Овај формат уредно смешта све 7-битне ASCII карактере у погодне 8-битне бајтове. Остали могући формати; 8 битова података, плус бит парности могу пренети све 8-битне вредности бајта.

У контексту серијских комуникација, парност се обично генерише и проверава од стране интерфејса хардвера (нпр. UART) и, на пријему, резултат постаје доступан процесору (и тако, на пример, Оперативни систем) помоћу статуса бита у регистру хардвера у интерфејсу хардвера. Опоравак од грешке се обично ради тако што се поново пошаљу подаци, појединости којима обично барата софтвер (нпр. оперативни систем У/И рутина).

RAID[уреди]

Парност података се користи при одређеним RAID нивоима да би се постигла редундантност. Ако диск у низу не успе, преостали подаци на другим дисковима могу се комбиновати са парношћу података (користећи Булову ЕКСИЛИ функцију) да реконструише податке који недостају.

На пример, претпоставимо да два диска од три диска РАИД 5 низа садрже следеће податке:

Диск 1: 01101101
Диск 2: 11010100

Да бисте израчунали парност података за два диска, ЕКСИЛИ се врши на њиховом подацима:

        01101101
ЕКСИЛИ 11010100
_____________
        10111001

Добијена парност податка, 10111001, је сачувана на Диску 3.

Уколико било који од три диска откаже, садржај пропалог диска може се реконструисати на копираном диску излагањем података из осталих дискова истим ЕКСИЛИ операцијама. Ако диск 2 откаже, његови подаци могу бити обновљени коришћењем садржаја ЕКСИЛИ резултата два преостала диска, диск 1 и диск 3:

Диск 1: 01101101
Диск 3: 10111001

као што следи:

        10111001
ЕКСИЛИ 01101101
_____________
        11010100

Резултат ЕКСИЛИ калкулације даје садржај Диска 2. 11010100 је сачувано на Диску 2, који је потпуно поправљен низ. Овај исти ЕКСИЛИ концепт се користи слично и у већим низовима, користећи било који број дискова. У случају RAID-а 3, низа од 12 дискова, 11 дискова учествују у ЕКСИЛИ калкулацијама приказаним горе и добијају вредност која се потом чува на наменском диску парности.

Историја[уреди]

"Стаза парности" је била присутна на првој магнетној траци за складиштење података, 1951. године. Парност у овом облику, примењена преко више паралелних сигнала, је позната као уздужна редундантна провера. Ово се може комбиновати са парности обрачунатој преко више битова послатих на један сигнал, уздужне редундантне провере. У паралелној магистрали, постоји једна уздужна редундантна провера бита по паралелном сигналу.

Парност се такође користила на неким папирним тракама (punched tape)које су служиле за унос података (којима су претходиле магнетне траке). На продатим системима Британске компаније ICL (раније ICT) Шаблон:Convert/LoffAoffDbSmid папир трака имала је 8 позиција рупа преко ње, 8. је била за парност. Осталих 7 позиција су коришћене за податке, нпр, 7-битни ASCII. Осма позиција је имала избушену рупу у зависности од броја избушених рупа за податке.

Насупрот мишљењу, Симор Креја, првог дизајнера суперрачунара, који није поштовао дизајнирање парности. То је показао на сирмоашном дизајну - ако дизајнирте своје путање преноса да буду поуздане, онда не морате да губите ресурсе на парности. Његов чувени цитат на ово (око 1963.) био је "Парност је за пољопривреднике" (после употребе термина "парности" у New Deal-у). Након што је касније укњучио бит парности на CDC 7600, Креј је наводно рекао: "Схватио сам да доста пољопривредника купује рачунаре".[1]

Види још[уреди]

Референце[уреди]

  1. ^ "The following UNVERIFIED quotes have been widely attributed to Seymour R. Cray." (dead)

Додатни линкови[уреди]