Хаминг кодтары: Сызықтық қателерді түзететін кодтар отбасы
Hamming code
Хаминг кодтары – компьютерлік қателерді түзету коды. Біт қателерін анықтап, түзетуге арналған, өте тиімді және жетілдірілген технология. 1950 ж. ойлап табылды.
Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Мазмұны
Кіріспе
Сызықтық қателерді түзейтін кодтар отбасысы
Family of linear error correcting codes
Компьютерлік ғылым және телекоммуникация саласында Хамминг кодтары – сызықтық қателерді түзейтін кодтар отбасысы. Хамминг кодтары бір биттік және екі биттік қателерді анықтауға, немесе түзетілмеген қателерді анықтамай бір биттік қателерді түзетуге мүмкіндік береді. Керісінше, қарапайым паритет коды қателерді түзете алмайды және тек қатедегі биттердің тақ санын ғана анықтай алады. Хамминг кодтары – кемел кодтар, яғни олар блок ұзындығы мен ең аз қашықтығы үшке тең кодтар үшін ең жоғары мүмкін жылдамдыққа жетеді. Ричард У. Хамминг 1950 жылы перфокарта оқылатын кезде туындаған қателерді автоматты түрде түзету үшін Хамминг кодтарын ойлап тапты. Өзінің алғашқы мақаласында Хамминг өзінің жалпы идеясын кеңейтті, бірақ ерекше назарды төрт бит дерекке үш паритет битін қосатын Хамминг (7,4) кодына бөлді. Математикалық тұрғыдан алғанда, Хамминг кодтары – екілік сызықтық кодтар класы. Кез келген r ≥ 2 бүтін саны үшін блок ұзындығы және хабарлама ұзындығы бар код сөзі бар. Сондықтан Хамминг кодтарының жылдамдығы , ең аз қашықтығы үшке тең кодтар үшін ең жоғары мүмкін (яғни, кез келген код сөзінен кез келген басқа код сөзіне өту үшін қажетті биттердің ең аз саны үш) және блок ұзындығы 2^(r) − 1-ге тең. Хамминг кодының теңдік тексеру матрицасы r ұзындығындағы нөлдік емес барлық бағандарды тізімдеу арқылы құрастырылады, яғни Хамминг кодының дуалды коды қысқартылған Хадамард коды, сондай-ақ Симплекс коды деп те аталады. Теңдік тексеру матрицасының екі кез келген бағаны жұптық сызықтық тәуелсіз болады. Хамминг кодтары деректерге шектеулі артық ақпарат қосатындықтан, олар тек қате деңгейі төмен болғанда ғана қателерді анықтап, түзетуге болады. Бұл компьютерлік жадта (әдетте RAM) орын алады, онда биттік қателер өте сирек кездеседі және Хамминг кодтары кеңінен қолданылады, ал осы түзету жүйесі бар RAM – ECC RAM (ECC жады). Осы контексте, көбінесе бір қосымша паритет биті бар кеңейтілген Хамминг коды қолданылады. Кеңейтілген Хамминг кодтары төрттік Хамминг қашықтығына жетеді, бұл декодерге ең көп дегенде бір биттік қате болған кезде және кез келген екі биттік қате болған кезде ажыратуға мүмкіндік береді. Осы мағынада кеңейтілген Хамминг кодтары бір қатені түзету және екі қатені анықтау (SECDED) болып табылады.
In computer science and telecommunication, Hamming codes are a family of linear error correcting codes. Hamming codes can detect one bit and two bit errors, or correct one bit errors without detection of uncorrected errors. By contrast, the simple parity code cannot correct errors, and can detect only an odd number of bits in error. Hamming codes are perfect codes, that is, they achieve the highest possible rate for codes with their block length and minimum distance of three. Richard W. Hamming invented Hamming codes in 1950 as a way of automatically correcting errors introduced by punched card readers. In his original paper, Hamming elaborated his general idea, but specifically focused on the Hamming(7,4) code which adds three parity bits to four bits of data. In mathematical terms, Hamming codes are a class of binary linear code. For each integer r ≥ 2 there is a code word with block length and message length Hence the rate of Hamming codes is , which is the highest possible for codes with minimum distance of three (i. e., the minimal number of bit changes needed to go from any code word to any other code word is three) and block length 2^(r) − 1. The parity check matrix of a Hamming code is constructed by listing all columns of length r that are non zero, which means that the dual code of the Hamming code is the shortened Hadamard code, also known as a Simplex code. The parity check matrix has the property that any two columns are pairwise linearly independent. Due to the limited redundancy that Hamming codes add to the data, they can only detect and correct errors when the error rate is low. This is the case in computer memory (usually RAM), where bit errors are extremely rare and Hamming codes are widely used, and a RAM with this correction system is an ECC RAM (ECC memory). In this context, an extended Hamming code having one extra parity bit is often used. Extended Hamming codes achieve a Hamming distance of four, which allows the decoder to distinguish between when at most one one bit error occurs and when any two bit errors occur. In this sense, extended Hamming codes are single error correcting and double error detecting, abbreviated as SECDED.
Тарих
Ричард Хамминг, Хамминг кодтарын ойлап тапқан адам, 1940 жылдардың соңында Белл зертханасында Белл Модель V компьютерімен жұмыс істеді, бұл электромеханикалық релелерге негізделген машина және оның циклдық уақыты секундтармен өлшенетін. Деректер енгізілуі ені жеті сегізден бір дюйм болатын, бір қатарға алты тесігі бар перфорацияланған қағаз лента арқылы жүзеге асырылды. Жұмыс күндері релелерде қателер анықталғанда, машина тоқтап, операторлардың мәселені түзетуі үшін шамдар жыпылықтайтын. Жұмыс сағаттарынан кейін және демалыс күндері операторлар болмағанда, машина келесі тапсырмаға көшетін. Хамминг демалыс күндері жұмыс істеді және анықталған қателерге байланысты бағдарламаларын бастапқы күйінен қайта іске қосуға мән берді. Бір жазбада Хамминг: "Егер машина қатені анықтай алса, неге ол қате орнын тауып, оны түзетуге болмайды?" деді. Келесі бірнеше жылда ол қателерді түзету мәселесімен айналысып, күшті алгоритмдер жиынтығын жасады. 1950 жылы ол қазір Хамминг коды деп аталатын және ECC жады сияқты қолданыстарда бүгінге дейін қолданылып келе жатқан кодты жариялады.
Richard Hamming, the inventor of Hamming codes, worked at Bell Labs in the late 1940s on the Bell Model V computer, an electromechanical relay based machine with cycle times in seconds. Input was fed in on punched paper tape, seven eighths of an inch wide, which had up to six holes per row. During weekdays, when errors in the relays were detected, the machine would stop and flash lights so that the operators could correct the problem. During after hours periods and on weekends, when there were no operators, the machine simply moved on to the next job. Hamming worked on weekends, and grew increasingly frustrated with having to restart his programs from scratch due to detected errors. In a taped interview, Hamming said, "And so I said, 'Damn it, if the machine can detect an error, why can't it locate the position of the error and correct it?'". Over the next few years, he worked on the problem of error correction, developing an increasingly powerful array of algorithms. In 1950, he published what is now known as Hamming code, which remains in use today in applications such as ECC memory.
Хаммингке дейінгі кодтар
Хамминг кодтарына дейін бірнеше қарапайым қателерді анықтайтын кодтар қолданылды, бірақ ешқайсысы да Хамминг кодтарымен салыстырылатын тиімділікке бірдей кеңістікте қол жеткізе алмады.
A number of simple error detecting codes were used before Hamming codes, but none were as effective as Hamming codes in the same overhead of space.
Теңдік
Партитет бір битті қосады, ол алдыңғы деректердегі бірліктердің саны (мәні 1-ге тең бит позициялары) жұп немесе тақ екенін көрсетеді. Егер беріліс кезінде тақ саны биттер өңделсе, хабарламаның паритеті өзгереді және қате осы сәтте анықталуы мүмкін; алайда, өңделген бит паритет битінің өзі болуы мүмкін. Көбінесе қабылданған келісім бойынша, паритет мәні 1 болса, деректерде тақ саны бірлік бар екенін, ал 0 болса – жұп санын көрсетеді. Егер өңделген биттердің саны жұп болса, тексеру биті дұрыс болады және қате анықталмайды. Сонымен қатар, паритет қате қай битте болғанын көрсетпейді, тіпті оны анықтаса да. Деректерді толығымен жойып, бастапқыдан қайта берілуі керек. Құбылмалы беріліс ортасында сәтті берілу ұзаққа созылуы немесе мүлдем орын алмауы мүмкін. Дегенмен, паритетті тексерудің сапасы төмен болса да, ол тек бір битті пайдаланатындықтан, бұл әдіс ең аз қосымша шығындарды тудырады.
Parity adds a single bit that indicates whether the number of ones (bit positions with values of one) in the preceding data was even or odd. If an odd number of bits is changed in transmission, the message will change parity and the error can be detected at this point; however, the bit that changed may have been the parity bit itself. The most common convention is that a parity value of one indicates that there is an odd number of ones in the data, and a parity value of zero indicates that there is an even number of ones. If the number of bits changed is even, the check bit will be valid and the error will not be detected. Moreover, parity does not indicate which bit contained the error, even when it can detect it. The data must be discarded entirely and re transmitted from scratch. On a noisy transmission medium, a successful transmission could take a long time or may never occur. However, while the quality of parity checking is poor, since it uses only a single bit, this method results in the least overhead.
Бестен екі код
Бестен екі код – дәл үш 0 және екі 1-ден тұратын бес биттік кодтау схемасы. Бұл мүмкін болатын комбинациялардың санын қамтамасыз етеді, ол 0–9 цифрларын көрсетуге жеткілікті. Бұл схема барлық бір биттік қателерді, барлық тақ санмен нөмірленген биттік қателерді және кейбір жұп санмен нөмірленген биттік қателерді (мысалы, екі 1 биттің ауысуын) анықтай алады. Дегенмен, ол осы қателердің ешқайсысын түзете алмайды.
A two out of five code is an encoding scheme which uses five bits consisting of exactly three 0s and two 1s. This provides possible combinations, enough to represent the digits 0–9. This scheme can detect all single bit errors, all odd numbered bit errors and some even numbered bit errors (for example the flipping of both 1 bits). However it still cannot correct any of these errors.
Қайталау
Сол кезде қолданылған тағы бір код әрбір дерек битін дұрыс жіберілгенін қамтамасыз ету үшін бірнеше рет қайталап жіберді. Мысалы, егер жіберілетін дерек биті 1 болса, 1=n = 3 қайталау коды 111-ді жібереді. Егер алынған үш бит бірдей болмаса, жіберу кезінде қате пайда болған дегенді білдіреді. Егер арна жеткілікті таза болса, көбінесе әрбір үштік бірінде ғана өзгеріске ұшырайды. Сондықтан 001, 010 және 100 нөл битіне, ал 110, 101 және 011 бір битіне сәйкес келеді, көптеген бірдей таңбалардың ('0' немесе '1') саны дерек битінің қандай болу керектігін көрсетеді. Қателердің болуына қарамастан бастапқы хабарламаны қалпына келтіре алатын кодты қателерді түзету коды деп атайды. Бұл үш рет қайталанатын код – екі паритет биті болғандықтан және 1=22 − 2 − 1 = 1 дерек биті болғандықтан 1=m = 2 параметрін ұсынатын Хамминг коды. Дегенмен, мұндай кодтар барлық қателерді дұрыс түзетуге қабілетті емес. Мысалы, егер арна екі битті ауыстырып, қабылдағыш 001 алса, жүйе қателікті анықтайды, бірақ бастапқы бит 0 екенін дұрыс емес тұжырымдайды. Бит тізбегінің ұзындығын төртке дейін ұлғайтсақ, барлық екі биттік қателерді анықтай аламыз, бірақ оларды түзету мүмкін емес (паритет биттерінің саны жұп); бес битте барлық екі биттік қателерді анықтап, түзетуге болады, бірақ барлық үш биттік қателерді түзетуге болмайды. Сонымен қатар, паритет биті тізбегінің ұзындығын арттыру тиімсіз, өйткені бастапқы жағдайда өткізу қабілеті үш есеге төмендейді, ал қателерді анықтау және түзету үшін биттің қайталану санын арттырғанда тиімділік күрт төмендейді.
Another code in use at the time repeated every data bit multiple times in order to ensure that it was sent correctly. For instance, if the data bit to be sent is a 1, an 1=n = 3 repetition code will send 111. If the three bits received are not identical, an error occurred during transmission. If the channel is clean enough, most of the time only one bit will change in each triple. Therefore, 001, 010, and 100 each correspond to a 0 bit, while 110, 101, and 011 correspond to a 1 bit, with the greater quantity of digits that are the same ('0' or a '1') indicating what the data bit should be. A code with this ability to reconstruct the original message in the presence of errors is known as an error correcting code. This triple repetition code is a Hamming code with 1=m = 2, since there are two parity bits, and 1=22 − 2 − 1 = 1 data bit. Such codes cannot correctly repair all errors, however. In our example, if the channel flips two bits and the receiver gets 001, the system will detect the error, but conclude that the original bit is 0, which is incorrect. If we increase the size of the bit string to four, we can detect all two bit errors but cannot correct them (the quantity of parity bits is even); at five bits, we can both detect and correct all two bit errors, but not all three bit errors. Moreover, increasing the size of the parity bit string is inefficient, reducing throughput by three times in our original case, and the efficiency drops drastically as we increase the number of times each bit is duplicated in order to detect and correct more errors.
Сипаттама
Егер хабарламаға қателерді түзейтін биттер қосылса және егер бұл биттерді әртүрлі қате биттер әртүрлі қате нәтижелерін тудыратындай етіп орналастыруға болады, онда бұрыс биттерді анықтауға болады. Жеті биттік хабарламада жеті мүмкін бір биттік қате бар, сондықтан үш қателіктерді басқару биті қате болғанын ғана емес, сонымен қатар қандай бит қатенің себебі болғанын да көрсетуге мүмкіндік береді. Хамминг қолданыстағы кодтау схемаларын, оның ішінде екіден бес схемасын зерттеді және олардың принциптерін жалпылады. Алдымен, ол жүйені сипаттау үшін номенклатураны жасады, соның ішінде блок ішіндегі дерек биттерінің және қателерді түзету биттерінің санын қамтыды. Мысалы, паритет кез келген дерек сөзі үшін бір биттен тұрады, сондықтан ASCII сөздері жеті биттен тұратынын ескере отырып, Хамминг мұны (8,7) коды деп сипаттады, яғни сегіз биттен тұрады, оның жетісі дерек. Қайталау мысалы (3,1) болады, дәл осы логиканы қолдана отырып. Кодтың жылдамдығы – екінші санның бірінші санға бөлінуі, қайталау мысалында 1/3. Хамминг сондай-ақ екі немесе одан көп биттердің ауысуының проблемаларын байқады және оны «қашықтық» деп атады (қазір оны оның құрметіне Хамминг қашықтығы деп атайды). Паритеттің қашықтығы 2-ге тең, сондықтан бір биттің ауысуын анықтауға болады, бірақ түзетуге болмайды, ал екі биттің ауысуы байқалмайды. (3,1) қайталаудың қашықтығы 3-ке тең, себебі көзге көрінбейтін қателерсіз басқа код сөзін алу үшін үш битті бірдей үштікке ауыстыру қажет. Ол бір биттік қателерді түзетуге немесе екі биттік қателерді анықтауға мүмкіндік береді, бірақ түзетуге болмайды. (4,1) қайталауы (әр битті төрт рет қайталау) 4 қашықтыққа ие, сондықтан үш биттің ауысуын анықтауға болады, бірақ түзетуге болмайды. Бір топтағы үш биттің ауысуы кезінде, түзетуге тырысу қате код сөзін тудыруы мүмкін жағдайлар болуы мүмкін. Жалпы, k қашықтығы бар код k-1 қателерді анықтай алады, бірақ түзетуге болмайды. Хамминг бір уақытта екі мәселеге қызығушылық танытты: қашықтықты мүмкіндігінше арттыру, сонымен бірге кодтың жылдамдығын да мүмкіндігінше жоғарылату. 1940 жылдары ол бірнеше кодтау схемаларын жасады, олар қолданыстағы кодтарға қарағанда айтарлықтай жақсартулар болды. Оның барлық жүйелерінің кілті – паритет биттерін бір-бірімен жабыстыру, осылайша олар деректермен қатар бір-бірін де тексеруге мүмкіндік алды.
If more error correcting bits are included with a message, and if those bits can be arranged such that different incorrect bits produce different error results, then bad bits could be identified. In a seven bit message, there are seven possible single bit errors, so three error control bits could potentially specify not only that an error occurred but also which bit caused the error. Hamming studied the existing coding schemes, including two of five, and generalized their concepts. To start with, he developed a nomenclature to describe the system, including the number of data bits and error correction bits in a block. For instance, parity includes a single bit for any data word, so assuming ASCII words with seven bits, Hamming described this as an (8,7) code, with eight bits in total, of which seven are data. The repetition example would be (3,1), following the same logic. The code rate is the second number divided by the first, for our repetition example, 1/3. Hamming also noticed the problems with flipping two or more bits, and described this as the "distance" (it is now called the Hamming distance, after him). Parity has a distance of 2, so one bit flip can be detected but not corrected, and any two bit flips will be invisible. The (3,1) repetition has a distance of 3, as three bits need to be flipped in the same triple to obtain another code word with no visible errors. It can correct one bit errors or it can detect but not correct two bit errors. A (4,1) repetition (each bit is repeated four times) has a distance of 4, so flipping three bits can be detected, but not corrected. When three bits flip in the same group there can be situations where attempting to correct will produce the wrong code word. In general, a code with distance k can detect but not correct k − 1 errors. Hamming was interested in two problems at once: increasing the distance as much as possible, while at the same time increasing the code rate as much as possible. During the 1940s he developed several encoding schemes that were dramatic improvements on existing codes. The key to all of his systems was to have the parity bits overlap, such that they managed to check each other as well as the data.
Қосымша теңдікпен (SECDED) Хамминг кодтары
Хамминг кодтарының ең аз қашықтығы 3-ке тең, яғни декодер бір қатені анықтап, түзете алады, бірақ кейбір код сөздерінің екі биттік қатесін, басқа код сөздерінің бір биттік қатесінен ажырата алмайды. Осылайша, кейбір екі биттік қателер, бір биттік қателер ретінде қате түсініліп, түзетуге тырыспаса, анықталмайды. Осы кемшілікті жою үшін Хамминг кодтарын қосымша паритет битімен кеңейтуге болады. Бұл арқылы Хамминг кодының ең аз қашықтығын 4-ке дейін арттыруға болады, бұл декодерге бір биттік және екі биттік қателерді ажыратуға мүмкіндік береді. Осылайша декодер бір қатені анықтап, түзете алады, сонымен бірге екі қатені анықтай алады (бірақ түзете алмайды). Егер декодер қателерді түзетуге тырыспаса, үш биттік қателерді сенімді түрде анықтай алады. Егер декодер қателерді түзетсе, кейбір үш биттік қателер бір биттік қателерге айналып, бұрыс мәнге "түзеледі". Қателерді түзету – бұл сенімділік (үш биттік қателерді сенімді анықтау мүмкіндігі) пен төзімділік (бір биттік қателерге қарамастан жұмыс істеу қабілеті) арасындағы айырбас. Бұл кеңейтілген Хамминг коды компьютерлік жад жүйелерінде кеңінен қолданылды, 1961 жылы IBM 7030 Stretch компьютерінен бастап, ол SECDED (немесе SEC DED, бір қателікті түзету, екі қателікті анықтау деген аббревиатурадан) деп аталды. XXI ғасырдың серверлік компьютерлері, әдетте SECDED деңгейіндегі қорғанысты сақтай отырып, енді Хамминг әдісін қолданбайды, оның орнына ұзақ кодтық сөздермен (128-ден 256 битке дейінгі деректер) және өзгертілген теңгерімді паритет тексеру ағаштары бар жүйелерге сүйенеді. (72,64) Хамминг коды әлі де кейбір аппараттық жүйелерде, соның ішінде Xilinx FPGA отбасыларында қолданылады.
Hamming codes have a minimum distance of 3, which means that the decoder can detect and correct a single error, but it cannot distinguish a double bit error of some codeword from a single bit error of a different codeword. Thus, some double bit errors will be incorrectly decoded as if they were single bit errors and therefore go undetected, unless no correction is attempted. To remedy this shortcoming, Hamming codes can be extended by an extra parity bit. This way, it is possible to increase the minimum distance of the Hamming code to 4, which allows the decoder to distinguish between single bit errors and two bit errors. Thus the decoder can detect and correct a single error and at the same time detect (but not correct) a double error. If the decoder does not attempt to correct errors, it can reliably detect triple bit errors. If the decoder does correct errors, some triple errors will be mistaken for single errors and "corrected" to the wrong value. Error correction is therefore a trade off between certainty (the ability to reliably detect triple bit errors) and resiliency (the ability to keep functioning in the face of single bit errors). This extended Hamming code was popular in computer memory systems, starting with IBM 7030 Stretch in 1961, where it is known as SECDED (or SEC DED, abbreviated from single error correction, double error detection). Server computers in 21st century, while typically keeping the SECDED level of protection, no longer use the Hamming's method, relying instead on the designs with longer codewords (128 to 256 bits of data) and modified balanced parity check trees. The (72,64) Hamming code is still popular in some hardware designs, including Xilinx FPGA families.
[7,4] Хамминг коды
1950 жылы Хамминг [7,4] Хамминг кодын енгізді. Ол үш теңдік битін қосу арқылы төрт дерек битін жеті битке кодтайды. Бұрын түсіндірілгендей, ол бір биттік қателерді анықтап, түзете алады немесе бір және екі биттік қателерді анықтап (бірақ түзете алмайды). Жалпы теңдік битін қосса, ол [8,4] кеңейтілген Хамминг кодына айналады, ол SECDED болып табылады және бір биттік қателерді анықтап, түзете алады, ал екі биттік қателерді анықтайды (бірақ түзете алмайды).
In 1950, Hamming introduced the [7,4] Hamming code. It encodes four data bits into seven bits by adding three parity bits. As explained earlier, it can either detect and correct single bit errors or it can detect (but not correct) both single and double bit errors. With the addition of an overall parity bit, it becomes the [8,4] extended Hamming code which is SECDED and can both detect and correct single bit errors and detect (but not correct) double bit errors.