Знайте, Intuit, лекция, развитие на прости цифрови устройства

Развитието на контролната сума на калкулатора

Различни контролни суми са широко използвани в цифрови устройства и системи за контрол на коректността на съхранение или предаване на данни. Същността на този метод на контрол е проста: да съхраняваните или предаваните информационни масиви се присъединява към малък контролен код (обикновено между 1 и освобождаване от отговорност до 32 цифри), които навити съдържа информация за целия масив. Когато четете или получаване на масива отново изчислява същия код за проверка в същия алгоритъм. Ако това повторно изчислява код е равен на кода, който е прикрепен към масива, се приема, че масивът се съхранява или предава без грешки. Логиката е, както следва: код за потвърждение (известен също като контролна) е много по-малко контролирано спектър, така че изкривяване на вероятностите контролна е много по-малък, отколкото вероятността от набор от изкривяване. Ако, обаче, ще бъде изкривен като масив, както и контролна сума, вероятността, че тези нарушения няма да се видят в шах за повторно преброяване на гласовете е изключително малка. Има, обаче, вероятността, че масивът ще бъде изкривен на няколко места, така че контролната сума на това изкривяване не се променя, но вероятността е също така най-общо ниско.

Контролни суми се използват за съхраняване на данни в памет (RAM и постоянен), съхранение на данни на магнитен носител (поддръжка) в локални и глобални мрежи предава информация. В случай на контролна защита съхранява информация може да се определи, че (сектор файл на диска) на масива е счупен и не може да се използва. В случай на защита на контролна сума на информацията, предадена от приемника може да поиска повторно предаване на изкривена предавател масив.

Има много начини за изчисляване на контролната сума, различна степен на сложност на компютрите надеждност и откриване на грешки. Но най-широко използвани в настоящия момент, така наречения "метод цикличен контрол излишък" на, или CRC (Cyclic за Излишък), в които се прилага цикличен шах.

Цикличен контролна се изчислява както следва. Цялото тяло на информация, се разглеждат като едно N-битов двоичен номер, където N - брой битове във всички байтове на масива. За да се изчисли контролната сума е номер на N-малко се дели постоянно число (полином), избран по специален начин (но не само разделени, и модул 2). Коефициентът на този участък се отстранява и остатъкът се само използва като контролна.

Ние няма да навлизаме в математическата основа на метода. Заинтересованите читатели могат да се отнасят към литературата. Тук ние се отбележи само, че този метод открива единични грешки в масива с вероятност от 100%, както и всяка друга редица грешки с вероятност от около 1-2 -н. където п - брой битове контролна сума (това е вярно само при условие, че п е по-голямо от п, които, обаче, е почти винаги се извършва.). Например, когато п = 8, тази вероятност е 0,996 за п = 16, ще бъде равна на 0,999985 и за п = 32 тя ще ,9999999997672. С други думи, се откриват почти всички грешки.

Сега накратко обясни какво е модул 2. Нека масив (последователността от битове), както следва: 101 111 001 110 (за простота, ние отнеме малко). Номер, с което делът (обикновено се нарича полиномът на генератора) 10011. Как да приемате това избрал? Тя трябва да се дели по модул 2 без остатък само от един и себе си (това означава, че трябва да бъде проста от гледна точка на брой по модул 2). Bit полином се взема от един по-голям от необходимия малко контролна (остатъци от участък). Така че да се получи 8-битови остатъци на (8-битова контролна сума), трябва да се вземе 9-битов полином. В този случай, 5-битов полином, следователно, остатъкът е 4-битов. За 8-малко може да се използва остатък, например, полином 1 0001 или 1101 11D в 16-матрични код.

Modulo 2 се прави по същия начин, както обикновено за нас да се разделят "в колоната" (фиг. 14.6), но вместо изваждане в този случай, побитова модул 2, това означава, че всеки резултат малко е функция на изключителни или на съответната отношение на бита. Частното, не представлява интерес за нас, а останалата част, равна в нашия пример 1000 за цикличен шах.

Фиг. 14.6. Изчисляване на циклична контролна

Как да се практика изпълнява изчисляване на остатъка (КРС)? Можете да го направите на принципа даден тук дълго дивизия (хардуер или софтуер). Но във всеки случай това е доста тромав и бавен. За да се ускори процеса на изчисляване е възможно с помощта на табличен метод. За тази цел, маса с размер 2 N числа х н. където п - малко контролна. Принципът на изчисляване на числата в таблицата е много проста (раздел. 14.1).

Таблица 14.1. Таблично метод за изчисляване на контролната сума на цикличния

Данните в таблицата (брой)

Фиг. 14.7. Паралелно компютър 8-битов циклична контролна в ROM

За мулти-битов контролна използва все по-различен подход - изчисляване на последователен код, където масив от данни се подава към калкулатор последователно, малко по малко. Сериен контролна калкулатор е регистър смяна с обратна връзка от някои от битове чрез суматорите по модул 2 (т.е., XOR елементи). Общият брой на бита на регистъра за смяна трябва да бъде равна на контролната сума на малко изчислява (или, което е същото, да бъде една по-малко от дължината на думата на полинома се използва). Включването на обратна връзка се определя еднозначно от избран полином. Това е много подобен на генератора последователност на квази-случаен принцип.

Брой обратна смяна точки, определени от броя единици в полином (единица в най-маловажния бит се игнорира) и броя на битовете на преместващия регистър, от които са взети за обратна връзка сигнали се определя от броя на единични битове в полином код. За разлика от квази-случаен сигнал генератор, в този случай е необходимо да се смесват за изключителна или не функционира само обратна връзка сигнали, но и на входния сигнал данни в последователен код.

Фиг. 14.8. Сериен калкулатор 16-битов цикличен смяна контролна да се регистрирате

Фиг. 14.8 е пример за последователно калкулатор 16-битов циклична контролна при избрана полином 1 0001 0000 0010 0001 11021 или в 16-матрични код (отново до мъже-ЛИЗАЦИЯ га CCITT V.41). Тъй като код полином три единици (без LSB), е необходимо да се вземат три точки включвания за обратна връзка. Когато този брой битове на сменящия регистър за обратна връзка, които са свързани, определен от положението на отделните битове в полином. Преди да започнете работа на смени регистър трябва да бъдат нулирани (сигнал "-Resets"). Bits трябва да бъдат придружени от множество светлинни ефекти сигнал. След приключване на масива ще регистрира циклична контролна сума.

Може да изглежда, че такъв сериен компютър не е много удобно, поради факта, че данните в масива трябва да бъдат изпратени до него в последователен код. Въпреки това, той е сериен код предават данни в информационни мрежи, и по-последователни данни код, записани на магнитен носител. Ето защо, във всички тези случаи, серийните калкулатори са идеални.

Входящите бита Период масив по сериен компютър, не трябва да бъдат по-малко от сумата на забавяне елементи на регистъра за смяна и изключителни или на. В резултат на това на ограничение на скоростта изчисление цикличен шах е значително по-малък, отколкото в случай на паралелно калкулатор. Това също е недостатък на този метод на изчисление.