Перейти к контенту
§ 2. Передача данных ГДЗ по Информатике 11 класс. Углубленный уровень. В 2 ч. Поляков К.Ю.
8. Можно ли исправить ошибку, обнаружив неверное значение бита чётности?
Ответ
Однако исправить ошибку нельзя, потому что непонятно, в каком именно разряде она случилась. Если же изменилось два бита, чётность не меняется, и такая ошибка не обнаруживается. В длинной цепочке применение бита чётности позволяет обнаруживать нечётное число ошибок (1, 3, 5, …), а ошибки в чётном количестве разрядов остаются незамеченными.
From Wikipedia, the free encyclopedia
| 7 bits of data | (count of 1-bits) | 8 bits including parity | |
|---|---|---|---|
| even | odd | ||
| 0000000 | 0 | 00000000 | 00000001 |
| 1010001 | 3 | 10100011 | 10100010 |
| 1101001 | 4 | 11010010 | 11010011 |
| 1111111 | 7 | 11111111 | 11111110 |
A parity bit, or check bit, is a bit added to a string of binary code. Parity bits are a simple form of error detecting code. Parity bits are generally applied to the smallest units of a communication protocol, typically 8-bit octets (bytes), although they can also be applied separately to an entire message string of bits.
The parity bit ensures that the total number of 1-bits in the string is even or odd.[1] Accordingly, there are two variants of parity bits: even parity bit and odd parity bit. In the case of even parity, for a given set of bits, the bits whose value is 1 are counted. If that count is odd, the parity bit value is set to 1, making the total count of occurrences of 1s in the whole set (including the parity bit) an even number. If the count of 1s in a given set of bits is already even, the parity bit’s value is 0. In the case of odd parity, the coding is reversed. For a given set of bits, if the count of bits with a value of 1 is even, the parity bit value is set to 1 making the total count of 1s in the whole set (including the parity bit) an odd number. If the count of bits with a value of 1 is odd, the count is already odd so the parity bit’s value is 0. Even parity is a special case of a cyclic redundancy check (CRC), where the 1-bit CRC is generated by the polynomial x+1.
Parity[edit]
In mathematics parity can refer to the evenness or oddness of an integer, which, when written in its binary form, can be determined just by examining only its least significant bit.
In information technology parity refers to the evenness or oddness, given any set of binary digits, of the number of those bits with value one. Because parity is determined by the state of every one of the bits, this property of parity—being dependent upon all the bits and changing its value from even to odd parity if any one bit changes—allows for its use in error detection and correction schemes.
In telecommunications the parity referred to by some protocols is for error-detection. The transmission medium is preset, at both end points, to agree on either odd parity or even parity. For each string of bits ready to transmit (data packet) the sender calculates its parity bit, zero or one, to make it conform to the agreed parity, even or odd. The receiver of that packet first checks that the parity of the packet as a whole is in accordance with the preset agreement, then, if there was a parity error in that packet, requests a re-transmission of that packet.
In computer science the parity stripe or parity disk in a RAID provides error-correction. Parity bits are written at the rate of one parity bit per n bits, where n is the number of disks in the array. When a read error occurs, each bit in the error region is recalculated from its set of n bits. In this way, using one parity bit creates «redundancy» for a region from the size of one bit to the size of one disk. See § Redundant Array of Independent Disks below.
In electronics, transcoding data with parity can be very efficient, as XOR gates output what is equivalent to a check bit that creates an even parity, and XOR logic design easily scales to any number of inputs. XOR and AND structures comprise the bulk of most integrated circuitry.
Error detection[edit]
If an odd number of bits (including the parity bit) are transmitted incorrectly, the parity bit will be incorrect, thus indicating that a parity error occurred in the transmission. The parity bit is only suitable for detecting errors; it cannot correct any errors, as there is no way to determine which particular bit is corrupted. The data must be discarded entirely, and re-transmitted from scratch. On a noisy transmission medium, successful transmission can therefore take a long time, or even never occur. However, parity has the advantage that it uses only a single bit and requires only a number of XOR gates to generate. See Hamming code for an example of an error-correcting code.
Parity bit checking is used occasionally for transmitting ASCII characters, which have 7 bits, leaving the 8th bit as a parity bit.
For example, the parity bit can be computed as follows. Assume Alice and Bob are communicating and Alice wants to send Bob the simple 4-bit message 1001.
| Type of bit parity | Successful transmission scenario |
|---|---|
| Even parity |
Alice wants to transmit: 1001 and 1011 Alice computes parity bit value: 1+0+1+1 (mod 2) = 1 Alice adds parity bit and sends: Bob receives: 10010 and 10111 Bob computes parity: 1+0+1+1+1 (mod 2) = 0 Bob reports correct transmission after observing expected even result. |
| Odd parity |
Alice wants to transmit: 1001 and 1011 Alice computes parity bit value: 1+0+0+1 (+ 1 mod 2) = 1 1+0+1+1 (+ 1 mod 2) = 0 Alice adds parity bit and sends: Bob receives: 10011 and 10110 Bob computes overall parity: 1+0+1+1+0 (mod 2) = 1 Bob reports correct transmission after observing expected odd result. |
This mechanism enables the detection of single bit errors, because if one bit gets flipped due to line noise, there will be an incorrect number of ones in the received data. In the two examples above, Bob’s calculated parity value matches the parity bit in its received value, indicating there are no single bit errors. Consider the following example with a transmission error in the second bit using XOR:
| Type of bit parity error | Failed transmission scenario |
|---|---|
| Even parity
Error in the second bit |
Alice wants to transmit: 1001
Alice computes parity bit value: 1^0^0^1 = 0 Alice adds parity bit and sends: 10010 …TRANSMISSION ERROR… Bob receives: 11010 Bob computes overall parity: 1^1^0^1^0 = 1 Bob reports incorrect transmission after observing unexpected odd result. |
| Even parity
Error in the parity bit |
Alice wants to transmit: 1001
Alice computes even parity value: 1^0^0^1 = 0 Alice sends: 10010 …TRANSMISSION ERROR… Bob receives: 10011 Bob computes overall parity: 1^0^0^1^1 = 1 Bob reports incorrect transmission after observing unexpected odd result. |
There is a limitation to parity schemes. A parity bit is only guaranteed to detect an odd number of bit errors. If an even number of bits have errors, the parity bit records the correct number of ones, even though the data is corrupt. (See also Error detection and correction.) Consider the same example as before with an even number of corrupted bits:
| Type of bit parity error | Failed transmission scenario |
|---|---|
| Even parity
Two corrupted bits |
Alice wants to transmit: 1001
Alice computes even parity value: 1^0^0^1 = 0 Alice sends: 10010 …TRANSMISSION ERROR… Bob receives: 11011 Bob computes overall parity: 1^1^0^1^1 = 0 Bob reports correct transmission though actually incorrect. |
Bob observes even parity, as expected, thereby failing to catch the two bit errors.
Usage[edit]
Because of its simplicity, parity is used in many hardware applications where an operation can be repeated in case of difficulty, or where simply detecting the error is helpful. For example, the SCSI and PCI buses use parity to detect transmission errors, and many microprocessor instruction caches include parity protection. Because the I-cache data is just a copy of main memory, it can be disregarded and re-fetched if it is found to be corrupted.
In serial data transmission, a common format is 7 data bits, an even parity bit, and one or two stop bits. This format accommodates all the 7-bit ASCII characters in an 8-bit byte. Other formats are possible; 8 bits of data plus a parity bit can convey all 8-bit byte values.
In serial communication contexts, parity is usually generated and checked by interface hardware (e.g., a UART) and, on reception, the result made available to a processor such as the CPU (and so too, for instance, the operating system) via a status bit in a hardware register in the interface hardware. Recovery from the error is usually done by retransmitting the data, the details of which are usually handled by software (e.g., the operating system I/O routines).
When the total number of transmitted bits, including the parity bit, is even, odd parity has the advantage that the all-zeros and all-ones patterns are both detected as errors. If the total number of bits is odd, only one of the patterns is detected as an error, and the choice can be made based on which is expected to be the more common error.
RAID array[edit]
Parity data is used by RAID arrays (redundant array of independent/inexpensive disks) to achieve redundancy. If a drive in the array fails, remaining data on the other drives can be combined with the parity data (using the Boolean XOR function) to reconstruct the missing data.
For example, suppose two drives in a three-drive RAID 5 array contained the following data:
| Drive 1: | 01101101 |
| Drive 2: | 11010100 |
To calculate parity data for the two drives, an XOR is performed on their data:
| 01101101 | |
| XOR | 11010100 |
| 10111001 |
The resulting parity data, 10111001, is then stored on Drive 3.
Should any of the three drives fail, the contents of the failed drive can be reconstructed on a replacement drive by subjecting the data from the remaining drives to the same XOR operation. If Drive 2 were to fail, its data could be rebuilt using the XOR results of the contents of the two remaining drives, Drive 1 and Drive 3:
| Drive 1: | 01101101 |
| Drive 3: | 10111001 |
as follows:
| 10111001 | |
| XOR | 01101101 |
| 11010100 |
The result of that XOR calculation yields Drive 2’s contents. 11010100 is then stored on Drive 2, fully repairing the array.
XOR logic is also equivalent to even parity (because a XOR b XOR c XOR … may be treated as XOR(a,b,c,…) which is an n-ary operator which is true if and only if an odd number of arguments are true). So the same XOR concept above applies similarly to larger RAID arrays with parity, using any number of disks. In the case of a RAID 3 array of 12 drives, 11 drives participate in the XOR calculation shown above and yield a value that is then stored on the dedicated parity drive.
Extensions and variations on the parity bit mechanism «double,» «dual,» or «diagonal» parity, are used in RAID-DP.
History[edit]
A parity track was present on the first magnetic tape data storage in 1951. Parity in this form, applied across multiple parallel signals, is known as a transverse redundancy check. This can be combined with parity computed over multiple bits sent on a single signal, a longitudinal redundancy check. In a parallel bus, there is one longitudinal redundancy check bit per parallel signal.
Parity was also used on at least some paper-tape (punched tape) data entry systems (which preceded magnetic tape systems). On the systems sold by British company ICL (formerly ICT) the 1-inch-wide (25 mm) paper tape had 8 hole positions running across it, with the 8th being for parity. 7 positions were used for the data, e.g., 7-bit ASCII. The 8th position had a hole punched in it depending on the number of data holes punched.
See also[edit]
- BIP-8
- Parity function
- Single-event upset
- 8-N-1
- Check digit
References[edit]
- ^ Ziemer, RodgerE.; Tranter, William H. (17 March 2014). Principles of communication : systems, modulation, and noise (Seventh ed.). Hoboken, New Jersey. ISBN 9781118078914. OCLC 856647730.
External links[edit]
- Different methods of generating the parity bit, among other bit operations
From Wikipedia, the free encyclopedia
| 7 bits of data | (count of 1-bits) | 8 bits including parity | |
|---|---|---|---|
| even | odd | ||
| 0000000 | 0 | 00000000 | 00000001 |
| 1010001 | 3 | 10100011 | 10100010 |
| 1101001 | 4 | 11010010 | 11010011 |
| 1111111 | 7 | 11111111 | 11111110 |
A parity bit, or check bit, is a bit added to a string of binary code. Parity bits are a simple form of error detecting code. Parity bits are generally applied to the smallest units of a communication protocol, typically 8-bit octets (bytes), although they can also be applied separately to an entire message string of bits.
The parity bit ensures that the total number of 1-bits in the string is even or odd.[1] Accordingly, there are two variants of parity bits: even parity bit and odd parity bit. In the case of even parity, for a given set of bits, the bits whose value is 1 are counted. If that count is odd, the parity bit value is set to 1, making the total count of occurrences of 1s in the whole set (including the parity bit) an even number. If the count of 1s in a given set of bits is already even, the parity bit’s value is 0. In the case of odd parity, the coding is reversed. For a given set of bits, if the count of bits with a value of 1 is even, the parity bit value is set to 1 making the total count of 1s in the whole set (including the parity bit) an odd number. If the count of bits with a value of 1 is odd, the count is already odd so the parity bit’s value is 0. Even parity is a special case of a cyclic redundancy check (CRC), where the 1-bit CRC is generated by the polynomial x+1.
Parity[edit]
In mathematics parity can refer to the evenness or oddness of an integer, which, when written in its binary form, can be determined just by examining only its least significant bit.
In information technology parity refers to the evenness or oddness, given any set of binary digits, of the number of those bits with value one. Because parity is determined by the state of every one of the bits, this property of parity—being dependent upon all the bits and changing its value from even to odd parity if any one bit changes—allows for its use in error detection and correction schemes.
In telecommunications the parity referred to by some protocols is for error-detection. The transmission medium is preset, at both end points, to agree on either odd parity or even parity. For each string of bits ready to transmit (data packet) the sender calculates its parity bit, zero or one, to make it conform to the agreed parity, even or odd. The receiver of that packet first checks that the parity of the packet as a whole is in accordance with the preset agreement, then, if there was a parity error in that packet, requests a re-transmission of that packet.
In computer science the parity stripe or parity disk in a RAID provides error-correction. Parity bits are written at the rate of one parity bit per n bits, where n is the number of disks in the array. When a read error occurs, each bit in the error region is recalculated from its set of n bits. In this way, using one parity bit creates «redundancy» for a region from the size of one bit to the size of one disk. See § Redundant Array of Independent Disks below.
In electronics, transcoding data with parity can be very efficient, as XOR gates output what is equivalent to a check bit that creates an even parity, and XOR logic design easily scales to any number of inputs. XOR and AND structures comprise the bulk of most integrated circuitry.
Error detection[edit]
If an odd number of bits (including the parity bit) are transmitted incorrectly, the parity bit will be incorrect, thus indicating that a parity error occurred in the transmission. The parity bit is only suitable for detecting errors; it cannot correct any errors, as there is no way to determine which particular bit is corrupted. The data must be discarded entirely, and re-transmitted from scratch. On a noisy transmission medium, successful transmission can therefore take a long time, or even never occur. However, parity has the advantage that it uses only a single bit and requires only a number of XOR gates to generate. See Hamming code for an example of an error-correcting code.
Parity bit checking is used occasionally for transmitting ASCII characters, which have 7 bits, leaving the 8th bit as a parity bit.
For example, the parity bit can be computed as follows. Assume Alice and Bob are communicating and Alice wants to send Bob the simple 4-bit message 1001.
| Type of bit parity | Successful transmission scenario |
|---|---|
| Even parity |
Alice wants to transmit: 1001 and 1011 Alice computes parity bit value: 1+0+1+1 (mod 2) = 1 Alice adds parity bit and sends: Bob receives: 10010 and 10111 Bob computes parity: 1+0+1+1+1 (mod 2) = 0 Bob reports correct transmission after observing expected even result. |
| Odd parity |
Alice wants to transmit: 1001 and 1011 Alice computes parity bit value: 1+0+0+1 (+ 1 mod 2) = 1 1+0+1+1 (+ 1 mod 2) = 0 Alice adds parity bit and sends: Bob receives: 10011 and 10110 Bob computes overall parity: 1+0+1+1+0 (mod 2) = 1 Bob reports correct transmission after observing expected odd result. |
This mechanism enables the detection of single bit errors, because if one bit gets flipped due to line noise, there will be an incorrect number of ones in the received data. In the two examples above, Bob’s calculated parity value matches the parity bit in its received value, indicating there are no single bit errors. Consider the following example with a transmission error in the second bit using XOR:
| Type of bit parity error | Failed transmission scenario |
|---|---|
| Even parity
Error in the second bit |
Alice wants to transmit: 1001
Alice computes parity bit value: 1^0^0^1 = 0 Alice adds parity bit and sends: 10010 …TRANSMISSION ERROR… Bob receives: 11010 Bob computes overall parity: 1^1^0^1^0 = 1 Bob reports incorrect transmission after observing unexpected odd result. |
| Even parity
Error in the parity bit |
Alice wants to transmit: 1001
Alice computes even parity value: 1^0^0^1 = 0 Alice sends: 10010 …TRANSMISSION ERROR… Bob receives: 10011 Bob computes overall parity: 1^0^0^1^1 = 1 Bob reports incorrect transmission after observing unexpected odd result. |
There is a limitation to parity schemes. A parity bit is only guaranteed to detect an odd number of bit errors. If an even number of bits have errors, the parity bit records the correct number of ones, even though the data is corrupt. (See also Error detection and correction.) Consider the same example as before with an even number of corrupted bits:
| Type of bit parity error | Failed transmission scenario |
|---|---|
| Even parity
Two corrupted bits |
Alice wants to transmit: 1001
Alice computes even parity value: 1^0^0^1 = 0 Alice sends: 10010 …TRANSMISSION ERROR… Bob receives: 11011 Bob computes overall parity: 1^1^0^1^1 = 0 Bob reports correct transmission though actually incorrect. |
Bob observes even parity, as expected, thereby failing to catch the two bit errors.
Usage[edit]
Because of its simplicity, parity is used in many hardware applications where an operation can be repeated in case of difficulty, or where simply detecting the error is helpful. For example, the SCSI and PCI buses use parity to detect transmission errors, and many microprocessor instruction caches include parity protection. Because the I-cache data is just a copy of main memory, it can be disregarded and re-fetched if it is found to be corrupted.
In serial data transmission, a common format is 7 data bits, an even parity bit, and one or two stop bits. This format accommodates all the 7-bit ASCII characters in an 8-bit byte. Other formats are possible; 8 bits of data plus a parity bit can convey all 8-bit byte values.
In serial communication contexts, parity is usually generated and checked by interface hardware (e.g., a UART) and, on reception, the result made available to a processor such as the CPU (and so too, for instance, the operating system) via a status bit in a hardware register in the interface hardware. Recovery from the error is usually done by retransmitting the data, the details of which are usually handled by software (e.g., the operating system I/O routines).
When the total number of transmitted bits, including the parity bit, is even, odd parity has the advantage that the all-zeros and all-ones patterns are both detected as errors. If the total number of bits is odd, only one of the patterns is detected as an error, and the choice can be made based on which is expected to be the more common error.
RAID array[edit]
Parity data is used by RAID arrays (redundant array of independent/inexpensive disks) to achieve redundancy. If a drive in the array fails, remaining data on the other drives can be combined with the parity data (using the Boolean XOR function) to reconstruct the missing data.
For example, suppose two drives in a three-drive RAID 5 array contained the following data:
| Drive 1: | 01101101 |
| Drive 2: | 11010100 |
To calculate parity data for the two drives, an XOR is performed on their data:
| 01101101 | |
| XOR | 11010100 |
| 10111001 |
The resulting parity data, 10111001, is then stored on Drive 3.
Should any of the three drives fail, the contents of the failed drive can be reconstructed on a replacement drive by subjecting the data from the remaining drives to the same XOR operation. If Drive 2 were to fail, its data could be rebuilt using the XOR results of the contents of the two remaining drives, Drive 1 and Drive 3:
| Drive 1: | 01101101 |
| Drive 3: | 10111001 |
as follows:
| 10111001 | |
| XOR | 01101101 |
| 11010100 |
The result of that XOR calculation yields Drive 2’s contents. 11010100 is then stored on Drive 2, fully repairing the array.
XOR logic is also equivalent to even parity (because a XOR b XOR c XOR … may be treated as XOR(a,b,c,…) which is an n-ary operator which is true if and only if an odd number of arguments are true). So the same XOR concept above applies similarly to larger RAID arrays with parity, using any number of disks. In the case of a RAID 3 array of 12 drives, 11 drives participate in the XOR calculation shown above and yield a value that is then stored on the dedicated parity drive.
Extensions and variations on the parity bit mechanism «double,» «dual,» or «diagonal» parity, are used in RAID-DP.
History[edit]
A parity track was present on the first magnetic tape data storage in 1951. Parity in this form, applied across multiple parallel signals, is known as a transverse redundancy check. This can be combined with parity computed over multiple bits sent on a single signal, a longitudinal redundancy check. In a parallel bus, there is one longitudinal redundancy check bit per parallel signal.
Parity was also used on at least some paper-tape (punched tape) data entry systems (which preceded magnetic tape systems). On the systems sold by British company ICL (formerly ICT) the 1-inch-wide (25 mm) paper tape had 8 hole positions running across it, with the 8th being for parity. 7 positions were used for the data, e.g., 7-bit ASCII. The 8th position had a hole punched in it depending on the number of data holes punched.
See also[edit]
- BIP-8
- Parity function
- Single-event upset
- 8-N-1
- Check digit
References[edit]
- ^ Ziemer, RodgerE.; Tranter, William H. (17 March 2014). Principles of communication : systems, modulation, and noise (Seventh ed.). Hoboken, New Jersey. ISBN 9781118078914. OCLC 856647730.
External links[edit]
- Different methods of generating the parity bit, among other bit operations
См.
в лекциях Эллины
11. Контроль четности. Двумерный контроль четности
Возможно, простейшая форма обнаружения
ошибок заключается в использовании
одного бита четности. Предположим, что
на рис. 5.4 передаваемые данные D имеют
длину d разрядов. При проверке на четность
отправитель просто добавляет к данным
один бит, значение которого вычисляется
как сумма всех d разрядов данных по
модулю 2. В этом случае количество единиц
в получающемся в результате числе всегда
будет четным. Применяются также схемы,
в которых контрольный бит инвертируется,
в результате чего количество единиц в
получающемся в результате числе всегда
будет нечетным. На рис. 5.5 изображена
схема проверки на четность, а единственный
бит четности хранится в отдельном поле.
Действия, выполняемые получателем
при использовании такой схемы, также
очень просты. Получатель должен всего
лишь сосчитать количество единиц в
полученных d + 1 разрядах. Если при проверке
на четность получатель обнаруживает,
что в принятых им данных нечетное
количество единичных разрядов, он
понимает, что произошла ошибка, по
меньшей мере, в одном разряде. В общем
случае это означает, что в полученных
данных инвертировано нечетное количество
разрядов (произошла ошибка нечетной
кратности).
Что произойдет, если в полученном
пакете данных произойдет четное
количество однобитовых ошибок? В этом
случае получатель не сможет обнаружить
ошибку. Если вероятность ошибки в одном
разряде мала и можно предположить, что
ошибки в отдельных разрядах возникают
независимо друг от друга, тогда вероятность
нескольких ошибок в одном пакете крайне
мала. В таком случае единственного бита
четности может быть достаточно. Однако
практические наблюдения показали, что
в действительности ошибки не являются
независимыми, а часто группируются в
пакеты ошибок. В случае пакетных ошибок
вероятность того, что получатель не
обнаружит ошибку в пакете, может
приблизиться к величине 50 %. Очевидно,
в такой ситуации требуется более надежная
схема обнаружения ошибок! Но прежде чем
перейти к изучению схем обнаружения
ошибок, применяемых на практике,
рассмотрим простую схему, которая
обобщает предыдущую схему одноразрядного
контроля четности и помогает понять
принцип работы методов исправления
ошибок.
На рис. 5.6 показано двухмерное обобщение
одноразрядной схемы проверки на четность.
В данной схеме d разрядов пакета данных
разделяются на г строк и j столбцов,
образуя прямоугольную матрицу. Значение
четности вычисляется для каждой строки
и каждого столбца. Получающиеся в
результате i +j +1 битов четности образуют
разряды обнаружения ошибок кадра
канального уровня.
Предположим теперь, что в исходном
блоке данных из d разрядов происходит
однократная ошибка. В такой двухмерной
схеме контроля четности об ошибке будут
одновременно сигнализировать контрольные
разряды строки и столбца. Таким образом,
получатель сможет не только обнаружить
сам факт ошибки, но и по номерам строки
и столбца найти поврежденный бит данных
и исправить его! На рисунке показан
пример, в котором поврежден бит в позиции
(2, 2) — он изменил свое значение с 1 на 0.
Такую одиночную ошибку получатель может
не только обнаружить, но и исправить.
Хотя нас, в первую очередь, интересует
обнаружение и исправление ошибок в
исходных d разрядах, данная схема
позволяет также обнаруживать и исправлять
одиночные ошибки в самих битах четности.
Кроме того, данная двухмерная схема
контроля четности позволяет обнаруживать
(но не исправлять!) любые комбинации из
двух одиночных ошибок (то есть двойные
ошибки) в пакете.
Способность приемника обнаруживать
и исправлять ошибки иногда называют
прямым исправлением ошибок (Forward Error
Correction, FEC). Подобные приемы широко
применяются в устройствах хранения и
воспроизведения звука, например на
лазерных компакт-дисках. В сетях методы
обнаружения и исправления ошибок могут
использоваться сами по себе, а также в
сочетании с автоматическими запросами
на повторную передачу. Методы обнаружения
и исправления ошибок очень полезны так
как позволяют снизить необходимое
количество повторных передач. Кроме
того (что, возможно, даже важнее), эти
методы позволяют получателю немедленно
исправлять ошибки. Таким образом,
получатель данных может не ждать, пока
отправитель получит его сообщение об
ошибке и вышлет пакет еще раз, что может
быть существенным преимуществом в
сетевых приложениях реального времени.
Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]
- #
- #
- #
- #
- #
- #
- #
- #
- #
- #
- #
Бит четности является параметром со значением 0 или 1 , который используется в способе обнаружения ошибок передачи , в которой 0 или 1 добавляется к каждой группе 7-8 битов (байт). Цель состоит в том, чтобы каждый байт всегда имел нечетное общее количество «1» или четное общее количество «1» в соответствии с установленной четностью.
Четность — это метод обнаружения ошибок, используемый в асинхронной связи. Он используется для проверки целостности каждого байта в передаваемом потоке. Например, если установлена нечетная четность, любой байт, полученный из передачи с общим числом «1», который является четным, должен содержать ошибку.
Источник: pixabay.com
Используются два типа проверки на четность: проверка на четность, при которой бит четности 1 добавляется, если в предыдущем байте имеется нечетное общее количество битов «1», и проверка на четность, когда выполняется обратное. С помощью этого метода вы сможете узнать только то, что произошла ошибка, но вы не узнаете, где произошла ошибка.
Для чего нужен бит четности?
При отправке цифровых данных может быть ошибка между переданным кодом и полученным кодом. Существует множество источников ошибок в виде различных типов шума, таких как электромагнитный шум или тепловой шум.
Следовательно, необходимо реализовать некоторый метод, чтобы проверить, ошибочны ли полученные коды или байты.
Однако как получатель может узнать, ошибочен ли полученный код? Получатель не может узнать код до его получения.
Например, предположим, что отправитель передает код 01100110, но после прохождения через зашумленную линию получатель получает код 00100110. Получатель не будет знать, что он получил код с ошибкой во втором бите.
Получатель не может знать, что сообщение содержит ошибку в первом бите, потому что это будет означать, что получатель уже знает сообщение от передатчика до передачи.
Контроль ошибок
Проблема, с которой приемник может проверить наличие ошибки, может быть решена с помощью кодирования с контролем ошибок.
Основная идея кодирования с контролем ошибок заключается в добавлении дополнительного бита в информацию, которая должна быть отправлена, чтобы ошибка обнаруживалась и исправлялась. Есть много кодировок обработки ошибок. Самый простой — это бит четности.
Бит четности добавляется к каждому передаваемому байту. Этот бит используется для проверки того, что информация была доставлена точно.
Бит четности для каждого байта устанавливается так, чтобы все байты имели нечетное число или четное число битов «1».
пример
Предположим, что два диска обмениваются данными с проверкой четности, которая является наиболее распространенной формой проверки четности.
В зависимости от единицы передачи он отправляет байты и сначала подсчитывает количество битов «1» в каждой группе из семи битов (байтах). Если количество битов «1» четное, установите бит четности в 0. Если количество битов «1» нечетное, установите бит четности в 1. Таким образом, каждый байт будет иметь четное количество битов «1».
Приемник проверяет каждый байт, чтобы убедиться, что он имеет четное количество битов «1». Если в байте обнаружено нечетное количество битов «1», приемник будет знать, что во время передачи произошла ошибка.
Ранее и получатель, и отправитель должны были договориться об использовании проверки четности и о том, должна ли четность быть нечетной или четной. Если обе стороны не настроены с одинаковым чувством паритета, связь будет невозможна.
Обнаружение ошибок
Проверка четности — самый простой метод обнаружения ошибок связи.
Однако, хотя он может обнаруживать множество ошибок, он не является безошибочным, поскольку он не способен обнаруживать компоновку, когда четное количество битов в одном и том же байте изменяется из-за электрического шума.
Проверка четности используется не только при обмене данными, но и для тестирования запоминающих устройств. Например, многие персональные компьютеры выполняют проверку на четность всякий раз, когда байт данных считывается из памяти.
Как это работает?
Предположим, у вас есть 7-битные коды данных и дополнительный бит, который является битом четности, добавлен для формирования 8-битного кода данных. Можно использовать два метода: четность и нечетность.
В качестве образца можно взять метод четности. Вы поступили бы наоборот, если бы выбрали метод нечетной четности.
Метод четной четности
Этот метод указывает, что добавляемый бит четности должен быть таким, чтобы общая сумма «1» в окончательном коде была четной. Например:
Следовательно, для первого 7-битного кода: 0010010 с четным количеством «1» (2) переданный 8-битный код будет: 00100100 с четным количеством «1» (2).
Для 7-битного кода 1110110 с нечетным количеством «1» (5) переданный 8-битный код будет 11101101 с четным количеством «1» (6).
После того, как получатель получит 8 битов, он проверит количество «1» в полученном коде, если количество «1» четное, это означает, что ошибки нет, если количество нечетное, это означает, что ошибка.
Когда вычисленная четность полученного байта не совпадает со значением принятого бита четности, считается, что произошла ошибка четности, и обычно байт отбрасывается.
В случае ошибки приемник предупредит передатчик, чтобы он отправил код еще раз.
Не безошибочный
Однако у этих методов контроля четности есть недостаток: если код 1110110 преобразуется шумом линии в 11111001, вызывая 2-битную ошибку, то этот метод не может обнаружить, что ошибка произошла.
Четность хороша при обнаружении ошибок и всегда обнаруживает любое нечетное количество ошибок в полученном байте. Однако при четном количестве ошибок средство проверки четности не сможет найти ошибку.
Ссылки
- Ванги Бил (2019). Проверка четности. Webopedia. Взято с: webopedia.com.
- Группа исследований электроники (2019). Четность символов. Взято с: erg.abdn.ac.uk.
- Словарь (2019) .. Бит паритета. Взято с сайта vocabulary.com.
- Ангмс (2013). Самый простой код контроля ошибок — Parity Bit. Взято с сайта angms.science.
- Кристенсон, (2011). Определение бита четности. Techterms. Взято с: techterms.com.
Мы знаем, что биты 0 и 1 соответствуют двум разным диапазонам аналоговых напряжений. Таким образом, во время передачи двоичных данных из одной системы в другую, шум также может быть добавлен. Из-за этого могут быть ошибки в полученных данных в другой системе.
Это означает, что бит 0 может измениться на 1 или бит 1 может измениться на 0. Мы не можем избежать помех от шума. Но мы можем сначала получить исходные данные, обнаружив, присутствуют ли какие-либо ошибки, а затем исправив эти ошибки. Для этой цели мы можем использовать следующие коды.
- Коды обнаружения ошибок
- Коды исправления ошибок
Коды обнаружения ошибок – используются для обнаружения ошибок, присутствующих в принятых данных (битовом потоке). Эти коды содержат некоторые биты, которые включены (добавлены) в исходный поток битов. Эти коды обнаруживают ошибку, если она произошла во время передачи исходных данных (потока битов). Пример – код четности, код Хэмминга.
Коды исправления ошибок – используются для исправления ошибок, присутствующих в полученных данных (битовом потоке), чтобы мы получили исходные данные. Коды исправления ошибок также используют аналогичную стратегию кодов обнаружения ошибок. Пример – код Хэмминга.
Поэтому, чтобы обнаружить и исправить ошибки, дополнительные биты добавляются к битам данных во время передачи.
Код паритета
Легко включить (добавить) один бит четности либо слева от MSB, либо справа от LSB исходного битового потока. Существует два типа кодов четности, а именно четный код четности и нечетный код четности, в зависимости от типа выбранной четности.
Четный код
Значение четного бита должно быть равно нулю, если в двоичном коде присутствует четное количество единиц. В противном случае он должен быть один. Таким образом, четное число единиц присутствует в четном коде четности . Четный код четности содержит биты данных и четный бит четности.
В следующей таблице приведены коды четности, соответствующие каждому 3-битному двоичному коду. Здесь бит четности включен справа от LSB двоичного кода.
| Бинарный код | Четный бит | Четный код |
|---|---|---|
| 000 | 0 | 0000 |
| 001 | 1 | 0011 |
| 010 | 1 | 0101 |
| 011 | 0 | 0110 |
| 100 | 1 | 1001 |
| 101 | 0 | 1010 |
| 110 | 0 | 1100 |
| 111 | 1 | 1111 |
Здесь число битов, присутствующих в четных кодах четности, равно 4. Таким образом, возможное четное число единиц в этих четных кодах четности равно 0, 2 и 4.
-
Если другая система получает один из этих четных кодов четности, то в полученных данных нет ошибки. Биты, отличные от четного бита, совпадают с битами двоичного кода.
-
Если другая система получит коды, отличные от четных, то в полученных данных возникнет ошибка (и). В этом случае мы не можем предсказать исходный двоичный код, потому что мы не знаем битовую позицию (ы) ошибки.
Если другая система получает один из этих четных кодов четности, то в полученных данных нет ошибки. Биты, отличные от четного бита, совпадают с битами двоичного кода.
Если другая система получит коды, отличные от четных, то в полученных данных возникнет ошибка (и). В этом случае мы не можем предсказать исходный двоичный код, потому что мы не знаем битовую позицию (ы) ошибки.
Поэтому четный бит четности полезен только для обнаружения ошибки в принятом коде четности. Но недостаточно исправить ошибку.
Код нечетного паритета
Значение нечетного бита четности должно быть нулевым, если в двоичном коде присутствует нечетное число единиц. В противном случае, он должен быть один. Так что нечетное количество единиц присутствует в нечетном коде четности . Нечетный код четности содержит биты данных и нечетный бит четности.
В следующей таблице показаны нечетные коды четности, соответствующие каждому 3-битному двоичному коду. Здесь нечетный бит четности включен справа от LSB двоичного кода.
| Бинарный код | Нечетный бит четности | Код нечетного паритета |
|---|---|---|
| 000 | 1 | 0001 |
| 001 | 0 | 0010 |
| 010 | 0 | 0100 |
| 011 | 1 | 0111 |
| 100 | 0 | 1000 |
| 101 | 1 | 1011 |
| 110 | 1 | 1101 |
| 111 | 0 | 1110 |
Здесь число битов, присутствующих в нечетных кодах четности, равно 4. Таким образом, возможное нечетное число единиц в этих нечетных кодах четности равно 1 и 3.
-
Если другая система получает один из этих нечетных кодов четности, то в полученных данных нет ошибки. Биты, отличные от нечетного бита четности, совпадают с битами двоичного кода.
-
Если другая система получает не четные коды четности, то в полученных данных есть ошибка (и). В этом случае мы не можем предсказать исходный двоичный код, потому что мы не знаем битовую позицию (ы) ошибки.
Если другая система получает один из этих нечетных кодов четности, то в полученных данных нет ошибки. Биты, отличные от нечетного бита четности, совпадают с битами двоичного кода.
Если другая система получает не четные коды четности, то в полученных данных есть ошибка (и). В этом случае мы не можем предсказать исходный двоичный код, потому что мы не знаем битовую позицию (ы) ошибки.
Следовательно, нечетный бит четности полезен только для обнаружения ошибки в принятом коде четности. Но недостаточно исправить ошибку.
Код Хэмминга
Код Хэмминга полезен как для обнаружения, так и для исправления ошибок, присутствующих в полученных данных. Этот код использует несколько битов четности, и мы должны поместить эти биты четности в позиции степеней 2.
Минимальное значение «k», для которого следующее соотношение является правильным (действительным), является не чем иным, как требуемым количеством битов четности.
2k geqn+k+1
Куда,
«n» – количество бит в двоичном коде (информация)
‘k’ – количество бит четности
Следовательно, количество битов в коде Хэмминга равно n + k.
Пусть код Хэмминга равен bn+kbn+k−1.....b3b2b1 и битам четности pk,pk−1,....p1. Мы можем поместить биты четности ‘k’ только в степени 2 позиции. В оставшихся битовых позициях мы можем разместить n бит двоичного кода.
Исходя из требований, мы можем использовать четную или нечетную четность при формировании кода Хемминга. Но тот же метод контроля четности следует использовать для того, чтобы определить, присутствует ли какая-либо ошибка в полученных данных.
Выполните эту процедуру для поиска битов четности .
-
Найдите значение p 1 , основанное на количестве единиц, присутствующих в позициях битов b 3 , b 5 , b 7 и так далее. Все эти битовые позиции (суффиксы) в их эквивалентном двоичном файле имеют «1» в значении места 2 0 .
-
Найдите значение p 2 , основанное на количестве единиц, присутствующих в позициях битов b 3 , b 6 , b 7 и так далее. Все эти битовые позиции (суффиксы) в их эквивалентном двоичном файле имеют «1» в значении места 2 1 .
-
Найдите значение p 3 , основанное на количестве единиц, присутствующих в позициях битов b 5 , b 6 , b 7 и так далее. Все эти битовые позиции (суффиксы) в их эквивалентном двоичном файле имеют «1» в значении места 2 2 .
-
Аналогично найдите другие значения битов четности.
Найдите значение p 1 , основанное на количестве единиц, присутствующих в позициях битов b 3 , b 5 , b 7 и так далее. Все эти битовые позиции (суффиксы) в их эквивалентном двоичном файле имеют «1» в значении места 2 0 .
Найдите значение p 2 , основанное на количестве единиц, присутствующих в позициях битов b 3 , b 6 , b 7 и так далее. Все эти битовые позиции (суффиксы) в их эквивалентном двоичном файле имеют «1» в значении места 2 1 .
Найдите значение p 3 , основанное на количестве единиц, присутствующих в позициях битов b 5 , b 6 , b 7 и так далее. Все эти битовые позиции (суффиксы) в их эквивалентном двоичном файле имеют «1» в значении места 2 2 .
Аналогично найдите другие значения битов четности.
Выполните эту процедуру для поиска контрольных битов .
-
Найдите значение c 1 , основанное на количестве единиц, присутствующих в битовых позициях b 1 , b 3 , b 5 , b 7 и так далее. Все эти битовые позиции (суффиксы) в их эквивалентном двоичном файле имеют «1» в значении места 2 0 .
-
Найдите значение c 2 , основанное на количестве единиц, присутствующих в позициях битов b 2 , b 3 , b 6 , b 7 и так далее. Все эти битовые позиции (суффиксы) в их эквивалентном двоичном файле имеют «1» в значении места 2 1 .
-
Найдите значение c 3 , основанное на количестве единиц, присутствующих в позициях битов b 4 , b 5 , b 6 , b 7 и так далее. Все эти битовые позиции (суффиксы) в их эквивалентном двоичном файле имеют «1» в значении места 2 2 .
-
Аналогично найдите другие значения контрольных битов.
Найдите значение c 1 , основанное на количестве единиц, присутствующих в битовых позициях b 1 , b 3 , b 5 , b 7 и так далее. Все эти битовые позиции (суффиксы) в их эквивалентном двоичном файле имеют «1» в значении места 2 0 .
Найдите значение c 2 , основанное на количестве единиц, присутствующих в позициях битов b 2 , b 3 , b 6 , b 7 и так далее. Все эти битовые позиции (суффиксы) в их эквивалентном двоичном файле имеют «1» в значении места 2 1 .
Найдите значение c 3 , основанное на количестве единиц, присутствующих в позициях битов b 4 , b 5 , b 6 , b 7 и так далее. Все эти битовые позиции (суффиксы) в их эквивалентном двоичном файле имеют «1» в значении места 2 2 .
Аналогично найдите другие значения контрольных битов.
Десятичный эквивалент контрольных битов в полученных данных дает значение позиции бита, где присутствует ошибка. Просто добавьте значение, присутствующее в этой позиции бита. Поэтому мы получим оригинальный двоичный код после удаления битов четности.
Пример 1
Найдем код Хемминга для двоичного кода: d 4 d 3 d 2 d 1 = 1000. Рассмотрим четные биты четности.
Количество битов в данном двоичном коде равно n = 4.
Мы можем найти необходимое количество бит четности, используя следующее математическое соотношение.
2k geqn+k+1
Подставим n = 4 в вышеприведенном математическом соотношении.
Rightarrow2k geq4+k+1
Rightarrow2k geq5+k
Минимальное значение k, удовлетворяющее указанному выше соотношению, равно 3. Следовательно, нам требуется 3 бита четности p 1 , p 2 и p 3 . Следовательно, количество битов в коде Хэмминга будет равно 7, поскольку в двоичном коде 4 бита и 3 бита четности. Мы должны поместить биты четности и биты двоичного кода в код Хэмминга, как показано ниже.
7-битный код Хэмминга : b7b6b5b4b3b2b1=d4d3d2p3D1р−2bp1
Подставляя биты двоичного кода, код Хэмминга будет b7b6b5b4b3b2b1=100p3Op2p1. Теперь давайте найдем биты четности.
p1=b7 oplusb5 oplusb3=1 oplus0 oplus0=1
p2=b7 oplusb6 oplusb3=1 oplus0 oplus0=1
p3=b7 oplusb6 oplusb5=1 oplus0 oplus0=1
Подставляя эти биты четности, код Хэмминга будет иметь значение b7b6b5b4b3b2b1=1001011.
Пример 2
В приведенном выше примере мы получили код Хэмминга в виде b7b6b5b4b3b2b1=1001011. Теперь давайте найдем позицию ошибки, когда полученный код равен b7b6b5b4b3b2b1=1001111.
Теперь давайте найдем контрольные биты.
c1=b7 oplusb5 oplusb3 oplusb1=1 oplus0 oplus1 oplus1=1
c2=b7 oplusb6 oplusb3 oplusb2=1 oplus0 oplus1 oplus1=1
c3=b7 oplusb6 oplusb5 oplusb4=1 oplus0 oplus0 oplus1=0
Десятичное значение контрольных битов дает позицию ошибки в полученном коде Хэмминга.
c3c2c1= left(011 right)2= left(3 right)10
Следовательно, ошибка присутствует в третьем бите (b 3 ) кода Хэмминга. Просто добавьте значение, присутствующее в этом бите, и удалите биты четности, чтобы получить исходный двоичный код.
|
|
эта статья нужны дополнительные цитаты для проверка. Пожалуйста помоги улучшить эту статью к добавление цитат в надежные источники. Материал, не полученный от источника, может быть оспорен и удален. |
| 7 бит данных | (количество 1 бит) | 8 бит, включая четность | |
|---|---|---|---|
| даже | странный | ||
| 0000000 | 0 | 00000000 | 00000001 |
| 1010001 | 3 | 10100011 | 10100010 |
| 1101001 | 4 | 11010010 | 11010011 |
| 1111111 | 7 | 11111111 | 11111110 |
А бит четности, или же проверить бит, это кусочек добавлен к строке бинарный код. Биты четности используются как простейшая форма код обнаружения ошибок. Биты четности обычно применяются к самым маленьким блокам протокола связи, обычно 8-битным. октеты (байты), хотя они также могут применяться отдельно ко всей цепочке битов сообщения.
Бит четности гарантирует, что общее количество единиц в строке равно четным или нечетным.[1] Соответственно, есть два варианта битов четности: бит четности и бит нечетной четности. В случае четности для данного набора битов подсчитываются вхождения битов, значение которых равно 1. Если этот счетчик нечетный, значение бита четности устанавливается в 1, в результате чего общее количество вхождений единиц во всем наборе (включая бит четности) становится четным. Если счетчик единиц в данном наборе битов уже является четным, значение бита четности равно 0. В случае нечетной четности кодирование меняется на противоположное. Для данного набора битов, если количество битов со значением 1 является четным, значение бита четности устанавливается в 1, что делает общее количество единиц во всем наборе (включая бит четности) нечетным числом. Если количество битов со значением 1 нечетное, счет уже нечетный, поэтому значение бита четности равно 0. Четность — это частный случай циклическая проверка избыточности (CRC), где 1-битный CRC генерируется многочлен Икс+1.
Если бит присутствует в точке, иначе выделенной для бита четности, но не используется для проверки четности, он может называться маркировать бит четности если бит четности всегда равен 1, или бит четности пространства если бит всегда равен 0. В таких случаях, когда значение бита постоянно, его можно назвать придерживаться бит четности хотя его функция не имеет ничего общего с четностью.[2] Функция таких битов зависит от конструкции системы, но примеры функций для таких битов включают в себя управление синхронизацией или идентификацию пакета как имеющего значение данных или адреса.[3] Если его фактическое значение бита не имеет отношения к его функции, бит составляет срок безразличия.[4]
Паритет
В математике паритет относится к четности или нечетности целого числа, которое для двоичное число определяется только младший бит. В телекоммуникациях и вычислительной технике четность относится к четности или нечетности числа битов со значением один в заданном наборе битов и, таким образом, определяется значением всех битов. Его можно рассчитать через XOR сумма битов, дающая 0 для четности и 1 для нечетной четности. Это свойство зависимости от всех битов и изменения значения при изменении любого одного бита позволяет использовать его в обнаружение ошибок схемы.
Обнаружение ошибок
Если нечетное количество бит (включая бит четности) переданный неправильно, бит четности будет неправильным, что указывает на то, что ошибка четности произошло в передаче. Бит четности подходит только для обнаружения ошибок; это не может правильный любые ошибки, так как невозможно определить, какой именно бит поврежден. Данные должны быть полностью отброшены, и ретранслировать с нуля. Следовательно, в шумной среде передачи успешная передача может занять много времени или даже не произойти. Однако у четности есть то преимущество, что она использует только один бит и требует только нескольких Ворота XOR генерировать. Видеть Код Хэмминга для примера кода исправления ошибок.
Проверка битов на четность иногда используется для передачи ASCII символы, которые имеют 7 бит, оставляя 8-й бит как бит четности.
Например, бит четности можно вычислить следующим образом. Предполагать Алиса и Боб общаются, и Алиса хочет отправить Бобу простое 4-битное сообщение 1001.
| Тип битовой четности | Сценарий успешной передачи |
|---|---|
| Четный паритет |
Алиса хочет передать: 1001 Алиса вычисляет значение бита четности: 1 + 0 + 0 + 1 (mod 2) = 0 Алиса добавляет бит четности и отправляет: 10010 Боб получает: 10010 Боб вычисляет четность: 1 + 0 + 0 + 1 + 0 (mod 2) = 0 Боб сообщает о правильной передаче после получения ожидаемого равномерного результата. |
| Нечетная четность |
Алиса хочет передать: 1001 Алиса вычисляет значение бита четности: 1 + 0 + 0 + 1 (mod 2) = 0 Алиса добавляет бит четности и отправляет: 10011 Боб получает: 10011 Боб вычисляет общую четность: 1 + 0 + 0 + 1 + 1 (mod 2) = 1 Боб сообщает о правильной передаче после наблюдения ожидаемого нечетного результата. |
Этот механизм позволяет обнаруживать одиночные битовые ошибки, потому что, если один бит перевернут из-за шума линии, в полученных данных будет неправильное количество единиц. В двух приведенных выше примерах вычисленное Бобом значение четности совпадает с битом четности в полученном значении, что указывает на отсутствие одиночных битовых ошибок. Рассмотрим следующий пример с ошибкой передачи во втором бите с использованием XOR:
| Тип битовой ошибки четности | Сценарий неудачной передачи |
|---|---|
| Четный паритет
Ошибка во втором бите |
Алиса хочет передать: 1001
Алиса вычисляет значение бита четности: 1 ^ 0 ^ 0 ^ 1 = 0 Алиса добавляет бит четности и отправляет: 10010 … ОШИБКА ПЕРЕДАЧИ … Боб получает: 11010 Боб вычисляет общую четность: 1 ^ 1 ^ 0 ^ 1 ^ 0 = 1 Боб сообщает о неправильной передаче после получения неожиданного нечетного результата. |
| Четный паритет
Ошибка в бите четности |
Алиса хочет передать: 1001
Алиса вычисляет значение четности: 1 ^ 0 ^ 0 ^ 1 = 0 Алиса отправляет: 10010 … ОШИБКА ПЕРЕДАЧИ … Боб получает: 10011 Боб вычисляет общую четность: 1 ^ 0 ^ 0 ^ 1 ^ 1 = 1 Боб сообщает о неправильной передаче после получения неожиданного нечетного результата. |
Есть ограничение на схемы четности. Бит четности гарантированно обнаруживает нечетное количество битовых ошибок. Если четное количество битов содержит ошибки, бит четности записывает правильное количество единиц, даже если данные повреждены. (Смотрите также обнаружение и исправление ошибок.) Рассмотрим тот же пример, что и раньше, с четным числом поврежденных битов:
| Тип битовой ошибки четности | Сценарий неудачной передачи |
|---|---|
| Четный паритет
Два поврежденных бита |
Алиса хочет передать: 1001
Алиса вычисляет значение четности: 1 ^ 0 ^ 0 ^ 1 = 0 Алиса отправляет: 10010 … ОШИБКА ПЕРЕДАЧИ … Боб получает: 11011 Боб вычисляет общую четность: 1 ^ 1 ^ 0 ^ 1 ^ 1 = 0 Боб сообщает о правильной передаче, хотя на самом деле неверной. |
Боб, как и ожидалось, наблюдает четность, тем самым не обнаруживая двух битовых ошибок.
Применение
Из-за своей простоты четность используется во многих аппаратное обеспечение приложения, в которых операция может быть повторена в случае затруднения, или где полезно простое обнаружение ошибки. Например, SCSI и Шины PCI использовать четность для обнаружения ошибок передачи, и многие микропроцессор инструкция тайники включить защиту четности. Поскольку I-cache данные — это просто копия основная память, его можно проигнорировать и повторно загрузить, если обнаружится, что он поврежден.
В серийный передача данных, общий формат — 7 бит данных, бит четности и один или два стоповые биты. Этот формат поддерживает все 7-битные ASCII символы в 8-битном байте. Возможны другие форматы; 8 бит данных плюс бит четности могут передавать все 8-битные байтовые значения.
В контексте последовательной связи четность обычно генерируется и проверяется аппаратным обеспечением интерфейса (например, UART ) и, при приеме, результат предоставляется процессор такие как ЦП (и то же самое, например, Операционная система ) через бит состояния в регистр оборудования в интерфейс аппаратное обеспечение. Восстановление после ошибки обычно осуществляется путем повторной передачи данных, детали которой обычно обрабатываются программным обеспечением (например, процедурами ввода-вывода операционной системы).
Когда общее количество переданных битов, включая бит четности, является четным, нечетная четность имеет то преимущество, что обе комбинации из нулей и все единицы обнаруживаются как ошибки. Если общее количество битов нечетное, только один из шаблонов обнаруживается как ошибка, и выбор может быть сделан на основе того, какая, как ожидается, будет более распространенной ошибкой.
Избыточный массив независимых дисков
Данные о четности используются некоторыми избыточный массив независимых дисков (RAID) уровни для достижения избыточность. Если диск в массиве выходит из строя, оставшиеся данные на других дисках можно объединить с данными четности (с помощью логического XOR функция), чтобы восстановить недостающие данные.
Например, предположим, что два диска в трех RAID 5 массив содержал следующие данные:
Привод 1: 01101101
Привод 2: 11010100
Чтобы вычислить данные о четности для двух дисков, над их данными выполняется XOR:
01101101
XOR 11010100
_____________
10111001
Полученные данные о четности, 10111001, затем сохраняется на Диске 3.
Если какой-либо из трех дисков выйдет из строя, содержимое неисправного диска может быть восстановлено на заменяющем диске, подвергнув данные с оставшихся дисков той же операции XOR. Если диск 2 выйдет из строя, его данные можно будет восстановить, используя результаты XOR содержимого двух оставшихся дисков, диска 1 и диска 3:
Привод 1: 01101101
Привод 3: 10111001
следующим образом:
10111001
XOR 01101101
_____________
11010100
Результат этого вычисления XOR дает содержимое диска 2. 11010100 затем сохраняется на Диске 2, полностью восстанавливая массив. Та же самая концепция XOR применима аналогично к большим массивам с использованием любого количества дисков. В случае массива RAID 3 из 12 дисков 11 дисков участвуют в вычислении XOR, показанном выше, и выдают значение, которое затем сохраняется на выделенном диске четности.
Расширения и вариации механизма битов четности «двойная», «двойная» или «диагональная» четность используются в RAID-DP.
История
«Трек паритета» присутствовал на первом хранение данных на магнитной ленте в 1951 г. Четность в этой форме, применяемая к нескольким параллельным сигналам, известна как поперечный контроль избыточности. Это можно комбинировать с проверкой четности, вычисляемой по нескольким битам, отправляемым в одном сигнале, проверка продольного дублирования. В параллельной шине на каждый параллельный сигнал приходится один бит проверки продольным избыточным кодом.
Четность также использовалась хоть на какой-то бумажной ленте (перфолента ) системы ввода данных (предшествовавшие системам на магнитной ленте). В системах, продаваемых британской компанией ICL (ранее ICT), бумажная лента шириной 1 дюйм (25 мм) имела 8 отверстий, проходящих через нее, причем 8-е было для проверки четности. Для данных использовалось 7 позиций, например, 7-битный ASCII. В 8-й позиции было пробито отверстие в зависимости от количества пробитых отверстий для данных.
Смотрите также
- БИП-8
- Функция четности
- Одно событие расстроено
- 8-Н-1
- Контрольная цифра
Рекомендации
- ^ Ziemer, RodgerE .; Трантер, Уильям Х. Принципы связи: системы, модуляция и шум (Седьмое изд.). Хобокен, Нью-Джерси. ISBN 9781118078914. OCLC 856647730.
- ^ «В чем разница между использованием четности меток или пробелов и без четности».[ненадежный источник? ]
- ^ «Какова цель Stick Parity?».
- ^ «Последовательная связь», Сб-дайджест, получено 2020-03-23
внешняя ссылка
- Различные методы генерации бита четности среди других битовых операций
Скорость передачи даных
Скорость передачи даных — это количество битов (байтов, Кбайт и т.д.), за 1 с).
Пропускная способность любого реального канала связи огранича. Это значит, что есть некоторая наибольшая возможная скорость передачи данных, которую принципиально невозможо превысить.
Основная единица измерения скорости — биты в секунду (бит/с, англ. bps — bits per second). Для характеристики быстродействующих каналов применяют килобиты в секунду (Кбит/с) и мегабиты в секунду (Мбит/с), иногда используют байты в секунду (байт/с) и килобайты в секунду (Кбайт/с).
Информационный объём I данных, переданных по каналу за время t , вычисляется по формуле I = v • t, где v — скорость передачи данных. Например, если скорость передачи данных равна 512 000 бит/с, за 1 минуту можно передать файл объёмом
512 000 бит/с • 60 с = 30 720 000 битов = 3 840 000 байтов = 3075 Кбайт.
Обнаружение ошибок
В реальных каналах связи всегда присутствуют помехи, искажающие сигнал. В некоторых случаях ошибки допустимы, например, при прослушивании радиопередачи через Интернет небольшое искажение звука не мешает понимать речь. Однако чаще всего требуется обеспечить точную передачу данных. Для этого в первую очередь нужно определить факт возникновения ошибки и, если это произошло, передать блок данных ещё раз.
Представьте себе, что получена цепочка нулей и единиц 1010101110, причём все биты независимы. В этом случае нет абсолютно никакой возможности определить, верно ли передана последовательность. Поэтому необходимо вводить избыточность в передаваемое сообщение (включать в него «лишние» биты) только для того, чтобы обнаружить ошибку.
Простейший вариант — добавить 1 бит в конце блока данных, который будет равен 1, если в основном сообщении нечётное число единиц, и равен 0 для сообщения с чётным числом единиц. Этот дополнительный бит называется битом чётности. Бит чётности используется при передаче данных в сетях, проверка чётности часто реализуется аппаратно (с помощью электроники).
Например, пусть требуется передать два бита данных. Возможны всего 4 разных сообщения: 00, 01, 10 и 11. Первое и четвёртое из них содержат чётное число единиц (0 и 2), значит, бит чётности для них равен 0. Во втором и третьем сообщениях нечётное число единиц (1), поэтому бит чётности будет равен 1. Таким образом, сообщения с добавленным битом чётности будут выглядеть так:
000, 011, 101, 110.
Первые два бита несут полезную информацию, а третий (подчёркнутый) — вспомогательный, он служит только для обнаружения ошибки. Обратим внимание, что каждое из этих трёхбитных сообщений содержит чётное число единиц.
Подумаем, сколько ошибок может обнаружить такой метод. Если при передаче неверно передан только один из битов, количество единиц в сообщении стало нечётным, это и служит признаком ошибки при передаче. Однако исправить ошибку нельзя, потому что непонятно, в каком именно разряде она случилась.
Если же изменилось два бита, чётность не меняется, и такая ошибка не обнаруживается. В длинной цепочке применение бита чётности позволяет обнаруживать нечётное число ошибок (1, 3, 5, …), а ошибки в чётном количестве разрядов остаются незамеченными.
Контроль с помощью бита чётности применяется для небольших блоков данных (чаще всего — для каждого отдельного байта) и хорошо работает тогда, когда отдельные ошибки при передаче независимы одна от другой и встречаются редко.
Для обнаружения искажений в передаче файлов, когда может сразу возникнуть множество ошибок, используют другой метод — вычисляют контрольную сумму с помощью какой-нибудь хэш-функции (вспомните материал учебника для 10 класса). Чаще всего для этой цели применяют алгоритмы CRC (англ. Cyclic Redundancy Code — циклический избыточный код), а также криптографические хэш-функции MD5, SHA-1 и другие. Если контрольная сумма блока данных, вычисленная приёмником, не совпадает с контрольной суммой, записанной передающей стороной, то произошла ошибка.
Помехоустойчивые коды.
Значительно сложнее исправить ошибку сразу (без повторной передачи), однако в некоторых случаях и эту задачу удаётся решить. Для этого требуется настолько увеличить избыточность кода (добавить «лишние» биты), что небольшое число ошибок всё равно позволяет достаточно уверенно распознать переданное сообщение. Например, несмотря на помехи в телефонной линии, обычно мы легко понимаем собеседника. Это значит, что речь обладает достаточно большой избыточностью, и это позволяет исправлять ошибки «на ходу».
Пусть, например, нужно передать один бит, 0 или 1. Утроим его, добавив ещё два бита, совпадающих с первым. Таким образом, получаются два «правильных» сообщения:
000 и 111.
Теперь посмотрим, что получится, если при передаче одного из битов сообщения 000 произодёт ошибка и приёмник получит искажённое сообщение 001. Заметим, что оно отличается одним битом от 000 и двумя битами от второго возможного варианта — 111. Значит, скорее всего, произошла ошибка в последнем бите и сообщение нужно исправить на 000. Если приёмник получил 101, можно точно сказать, что произошла ошибка, однако попытка исправить её приведёт к неверному варианту, так как ближайшая «правильная» последовательность — это 111. Таким образом, такой код обнаруживает одну или две ошибки. Кроме того, он позволяет исправить (!) одну ошибку, т. е. является помехоустойчивым.
Помехоустойчивый код — это код, который позволяет исправлять ошибки, если их количество не превышает некоторого уровня.
Выше мы фактически применили понятие «расстояния» между двумя кодами. В теории передачи информации эта величина называется расстоянием Хэмминга в честь американского математика Р. Хэмминга.
Расстояние Хэмминга — это количество позиций, в которых различаются два закодированных сообщения одинаковой длины.
Например, расстояние d между кодами 001 и 100 равно
d(001, 100) = 2,
потому что они различаются в двух битах (эти биты подчёркнуты). В приведённом выше примере расстояние между «правильными» последовательностями (словами) равно d(000, 111) = 3. Такой код позволяет обнаружить одну или две ошибки и исправить одну ошибку.
В общем случае, если минимальное расстояние между «правильными» словами равно d, можно обнаружить от 1 до d — 1 ошибок, потому что при этом полученный код будет отличаться от всех допустимых вариантов. Для исправления r ошибок необходимо, чтобы выполнялось условие
d ≥ 2r +1.
Это значит, что слово, в котором сделано r ошибок, должно быть ближе к исходному слову (из которого оно получено искажением), чем к любому другому.
Рассмотрим более сложный пример. Пусть нужно передавать три произвольных бита, обеспечив обнаружение двух любых ошибок и исправление одной ошибки. В этом случае можно использовать, например, такой код с тремя контрольными битами (они подчеркнуты);
000 000 100 101
001 111 101 010
010 011 110 110
011 100 111 001
Расстояние Хэмминга между любыми двумя словами в таблице не менее 3, поэтому код обнаруживает две ошибки и позволяет исправить одну. Как же вычислить ошибочный бит?
Предположим, что было получено кодовое слово 011011. Определив расстояние Хэмминга до каждого из «правильных» слов, находим единственное слово 010011, расстояние до которого равно 1 (расстояния до остальных слов больше). Значит, скорее всего, это слово и было передано, но исказилось из-за помех.
На практике используют несколько более сложные коды, которые называются кодами Хэмминга. В них информационные и контрольные биты перемешаны, и за счёт этого можно сразу, без перебора, определить номер бита, в котором произошла ошибка. Наиболее известен семибитный код, в котором 4 бита — это данные, а 3 бита — контрольные. В нём минимальное расстояние между словами равно 3, поэтому он позволяет обнаружить две ошибки и исправить одну.
Вопросы и задания
1. В каких единицах измеряют скорость передачи данных?
2. Почему для любого канала связи скорость передачи данных ограничена?
3. Как вычисляется информационный объем данных, который можно передать за некоторое время?
4. В каких случаях при передаче данных допустимы незначительные ошибки?
5. Что такое избыточность сообщения? Для чего её можно использовать? Приведите примеры.
6. Как помехи влияют на передачу данных?
7. Что такое бит чётности? В каких случаях с помощью бита чётности можно обнаружить ошибку, а в каких — нельзя?
8. Можно ли исправить ошибку, обнаружив неверное значение бита четности?
9. Для чего используется метод вычисления контрольной суммы?
10. Какой код называют помехоустойчивым?
11. Каково должно быть расстояние Хэмминга между двумя любыми кодами, чтобы можно было исправить две ошибки?
12. Как исправляется ошибка при использовании помехоустойчивого кода?
13. Сколько ошибок обнаруживает 7-битный код Хэмминга, описанный в конце параграфа, и сколько ошибок он позволяет исправить?
Подготовьте сообщение
а) «Алгоритмы CRC»
б) «Коды Хемминга»
Вернуться в главу
Block title |
|---|
Вход на сайт |
|---|
Поиск |
|---|
Календарь |
|||||||||||||||||||||||||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
|
Архив записей |
|---|
|
Статистика |
|---|
|
Онлайн всего: 1 Гостей: 1 Пользователей: 0 |
We know that the bits 0 and 1 corresponding to two different range of analog voltages. So, during transmission of binary data from one system to the other, the noise may also be added. Due to this, there may be errors in the received data at other system.
That means a bit 0 may change to 1 or a bit 1 may change to 0. We can’t avoid the interference of noise. But, we can get back the original data first by detecting whether any error(s) present and then correcting those errors. For this purpose, we can use the following codes.
- Error detection codes
- Error correction codes
Error detection codes − are used to detect the error(s) present in the received data (bit stream). These codes contain some bit(s), which are included (appended) to the original bit stream. These codes detect the error, if it is occurred during transmission of the original data (bit stream).Example − Parity code, Hamming code.
Error correction codes − are used to correct the error(s) present in the received data (bit stream) so that, we will get the original data. Error correction codes also use the similar strategy of error detection codes.Example − Hamming code.
Therefore, to detect and correct the errors, additional bit(s) are appended to the data bits at the time of transmission.
Parity Code
It is easy to include (append) one parity bit either to the left of MSB or to the right of LSB of original bit stream. There are two types of parity codes, namely even parity code and odd parity code based on the type of parity being chosen.
Even Parity Code
The value of even parity bit should be zero, if even number of ones present in the binary code. Otherwise, it should be one. So that, even number of ones present in even parity code. Even parity code contains the data bits and even parity bit.
The following table shows the even parity codes corresponding to each 3-bit binary code. Here, the even parity bit is included to the right of LSB of binary code.
| Binary Code | Even Parity bit | Even Parity Code |
|---|---|---|
| 000 | 0 | 0000 |
| 001 | 1 | 0011 |
| 010 | 1 | 0101 |
| 011 | 0 | 0110 |
| 100 | 1 | 1001 |
| 101 | 0 | 1010 |
| 110 | 0 | 1100 |
| 111 | 1 | 1111 |
Here, the number of bits present in the even parity codes is 4. So, the possible even number of ones in these even parity codes are 0, 2 & 4.
-
If the other system receives one of these even parity codes, then there is no error in the received data. The bits other than even parity bit are same as that of binary code.
-
If the other system receives other than even parity codes, then there will be an error(s) in the received data. In this case, we can’t predict the original binary code because we don’t know the bit position(s) of error.
Therefore, even parity bit is useful only for detection of error in the received parity code. But, it is not sufficient to correct the error.
Odd Parity Code
The value of odd parity bit should be zero, if odd number of ones present in the binary code. Otherwise, it should be one. So that, odd number of ones present in odd parity code. Odd parity code contains the data bits and odd parity bit.
The following table shows the odd parity codes corresponding to each 3-bit binary code. Here, the odd parity bit is included to the right of LSB of binary code.
| Binary Code | Odd Parity bit | Odd Parity Code |
|---|---|---|
| 000 | 1 | 0001 |
| 001 | 0 | 0010 |
| 010 | 0 | 0100 |
| 011 | 1 | 0111 |
| 100 | 0 | 1000 |
| 101 | 1 | 1011 |
| 110 | 1 | 1101 |
| 111 | 0 | 1110 |
Here, the number of bits present in the odd parity codes is 4. So, the possible odd number of ones in these odd parity codes are 1 & 3.
-
If the other system receives one of these odd parity codes, then there is no error in the received data. The bits other than odd parity bit are same as that of binary code.
-
If the other system receives other than odd parity codes, then there is an error(s) in the received data. In this case, we can’t predict the original binary code because we don’t know the bit position(s) of error.
Therefore, odd parity bit is useful only for detection of error in the received parity code. But, it is not sufficient to correct the error.
Hamming Code
Hamming code is useful for both detection and correction of error present in the received data. This code uses multiple parity bits and we have to place these parity bits in the positions of powers of 2.
The minimum value of ‘k’ for which the following relation is correct (valid) is nothing but the required number of parity bits.
$$2^kgeq n+k+1$$
Where,
‘n’ is the number of bits in the binary code (information)
‘k’ is the number of parity bits
Therefore, the number of bits in the Hamming code is equal to n + k.
Let the Hamming code is $b_{n+k}b_{n+k-1}…..b_{3}b_{2}b_{1}$ & parity bits $p_{k}, p_{k-1}, ….p_{1}$. We can place the ‘k’ parity bits in powers of 2 positions only. In remaining bit positions, we can place the ‘n’ bits of binary code.
Based on requirement, we can use either even parity or odd parity while forming a Hamming code. But, the same parity technique should be used in order to find whether any error present in the received data.
Follow this procedure for finding parity bits.
-
Find the value of p1, based on the number of ones present in bit positions b3, b5, b7 and so on. All these bit positions (suffixes) in their equivalent binary have ‘1’ in the place value of 20.
-
Find the value of p2, based on the number of ones present in bit positions b3, b6, b7 and so on. All these bit positions (suffixes) in their equivalent binary have ‘1’ in the place value of 21.
-
Find the value of p3, based on the number of ones present in bit positions b5, b6, b7 and so on. All these bit positions (suffixes) in their equivalent binary have ‘1’ in the place value of 22.
-
Similarly, find other values of parity bits.
Follow this procedure for finding check bits.
-
Find the value of c1, based on the number of ones present in bit positions b1, b3, b5, b7 and so on. All these bit positions (suffixes) in their equivalent binary have ‘1’ in the place value of 20.
-
Find the value of c2, based on the number of ones present in bit positions b2, b3, b6, b7 and so on. All these bit positions (suffixes) in their equivalent binary have ‘1’ in the place value of 21.
-
Find the value of c3, based on the number of ones present in bit positions b4, b5, b6, b7 and so on. All these bit positions (suffixes) in their equivalent binary have ‘1’ in the place value of 22.
-
Similarly, find other values of check bits.
The decimal equivalent of the check bits in the received data gives the value of bit position, where the error is present. Just complement the value present in that bit position. Therefore, we will get the original binary code after removing parity bits.
Example 1
Let us find the Hamming code for binary code, d4d3d2d1 = 1000. Consider even parity bits.
The number of bits in the given binary code is n=4.
We can find the required number of parity bits by using the following mathematical relation.
$$2^kgeq n+k+1$$
Substitute, n=4 in the above mathematical relation.
$$Rightarrow 2^kgeq 4+k+1$$
$$Rightarrow 2^kgeq 5+k$$
The minimum value of k that satisfied the above relation is 3. Hence, we require 3 parity bits p1, p2, and p3. Therefore, the number of bits in Hamming code will be 7, since there are 4 bits in binary code and 3 parity bits. We have to place the parity bits and bits of binary code in the Hamming code as shown below.
The 7-bit Hamming code is $b_{7}b_{6}b_{5}b_{4}b_{3}b_{2}b_{1}=d_{4}d_{3}d_{2}p_{3}d_{1}p_{2}bp_{1}$
By substituting the bits of binary code, the Hamming code will be $b_{7}b_{6}b_{5}b_{4}b_{3}b_{2}b_{1} = 100p_{3}Op_{2}p_{1}$. Now, let us find the parity bits.
$$p_{1}=b_{7}oplus b_{5}oplus b_{3}=1 oplus 0 oplus 0=1$$
$$p_{2}=b_{7}oplus b_{6}oplus b_{3}=1 oplus 0 oplus 0=1$$
$$p_{3}=b_{7}oplus b_{6}oplus b_{5}=1 oplus 0 oplus 0=1$$
By substituting these parity bits, the Hamming code will be $b_{7}b_{6}b_{5}b_{4}b_{3}b_{2}b_{1}= 1001011$.
Example 2
In the above example, we got the Hamming code as $b_{7}b_{6}b_{5}b_{4}b_{3}b_{2}b_{1}= 1001011$. Now, let us find the error position when the code received is $b_{7}b_{6}b_{5}b_{4}b_{3}b_{2}b_{1}= 1001111$.
Now, let us find the check bits.
$$c_{1}=b_{7}oplus b_{5}oplus b_{3}oplus b_{1}=1 oplus 0 oplus 1 oplus1 =1$$
$$c_{2}=b_{7}oplus b_{6}oplus b_{3}oplus b_{2}=1 oplus 0 oplus 1 oplus1 =1$$
$$c_{3}=b_{7}oplus b_{6}oplus b_{5}oplus b_{4}=1 oplus 0 oplus 0 oplus1 =0$$
The decimal value of check bits gives the position of error in received Hamming code.
$$c_{3}c_{2}c_{1} = left ( 011 right )_{2}=left ( 3 right )_{10}$$
Therefore, the error present in third bit (b3) of Hamming code. Just complement the value present in that bit and remove parity bits in order to get the original binary code.
Подборка по базе: баз данных 2021.pdf, СОГЛАСИЕ НА ОБРАБОТКУ ПЕРСОНАЛЬНЫХ ДАННЫХ.doc, Методика использования конвертации данных и планов обмена.doc, 2_Динамические структуры данных.doc, Реляционные базы данных (11 класс).pptx, Курсовая работа Защита персональных данных работников Мухина А. , Протокол учета пульсовых данных .docx, Алгоритмы и структуры данных Задание2.docx, Правовая информация о предоставлении персональных данных.docx, СОГЛАСИЕ НА ОБРАБОТКУ ПЕРСОНАЛЬНЫХ ДАННЫХ.docx
п 2 Передача данных
Харлова алина 11А
вопросы
1
2
3
4
5
6
7
8
9
выход
в1 Почему для любого канала связи скорость передачи данных ограничена?
Пропускная способность любого канала связи, в котором есть помехи, ограничена. Это значит, что есть некоторая наибольшая возможная скорость передачи данных, которую принципиально невозможно превысить. Зависит от аппаратуры и мощности помех. Не может быть больше скорости света.
назад
теория
в2 В каких случаях при передаче информации допустимы незначительные ошибки?
В реальных каналах связи всегда присутствуют помехи, искажающие сигнал. В некоторых случаях ошибки допустимы, например, при прослушивании радиопередачи через Интернет небольшое искажение звука не мешает понимать речь.
назад
теория
В3 что такое избыточность сообщения? Для чего ее можно использовать?
Избыточность – это превышение количества информации, используемой для передачи или хранения сообщения. приводит к увеличению времени передачи сообщений, уменьшению скорости передачи информации, излишней загрузки канала, вместе с тем, избыточность необходима для обеспечения достоверности передаваемых данных. Применяя специальные коды, использующие избыточность в передаваемых сообщениях, можно обнаружить и исправить ошибки.
назад
теория
В4 в каких случаях с помощью бита четности можно обнаружить ошибку, а в каких – нельзя?
Бит чётности позволяет обнаруживать нечётное число ошибок (1, 3, 5, …), а ошибки в чётном количестве разрядов остаются незамеченными. Контроль применяется для небольших блоков данных (чаще всего — для каждого отдельного байта) и хорошо работает тогда, когда отдельные ошибки при передаче независимы одна от другой и встречаются редко.
назад
теория
В5 можно ли исправить ошибку, обнаружив неверное значение бита четности?
Исправить ошибку нельзя, потому что непонятно, в каком именно разряде она случилась. Если же изменилось два бита, чётность не меняется, и такая ошибка не обнаруживается.
назад
теория
В6 как вы думаете, почему для контроля передачи файлов используются контрольные суммы, а не бит четности?
Используя бит четности, легко и быстро работать, но если произошло более одной ошибки, то ее можно не заметить. Используя контрольные суммы каждая ошибка будет обнаружена, но при передаче и получении нужно будет вычислять эту контрольную сумму, что приведет к временным затратам.
назад
теория
В7 каково должно быть расстояние хэмминга между двумя любыми кодами, чтобы можно было исправить 2 ошибки?
Минимальное расстояние Хэмминга выбирается из условия расстояние равно d . Условие d>= 2r+1 , где r кол-во ошибок. Поэтому d>=5, может либо исправлять однократные ошибки, либо только обнаруживать однократные и двукратные ошибки.
назад
теория
В8 как исправляется ошибка при использовании помехоустойчивого кода?
Для исправления ошибки нужно к символу разряда в котором произошла ошибка прибавить единицу по модулю два.
назад
теория
В9 какие достоинства и недостатки есть у кодов хэмминга с большим размером блоков?
Недостаток кода Хэмминга — некратность размера исходного блока кода и блока кода степени двойки. Это затрудняет обработку кодов Хэмминга на компьютерах, оперирующих блоками бит кратными степени двойки. Достоинство в том, что реализация алгоритма требует небольших ресурсов и может быть выполнена аппаратно. Исходными данными для кодирования является произвольная двоичная последовательность.
назад
теория
1 доп Теория
- Скорость передачи данных – это кол-во бит, которое передается по каналу связи за единицу времени.
- Пропускная способность канала связи – наибольшая возможная скорость передачи данных, которую принципиально невозможно превысить.
- Объем информации вычисляется по формуле I = u * t
назад
2 доп теория
Избыточность – включать в код « лишние биты », только для того чтобы найти ошибку.
Бит четности – дополнительный бит, используется при передачи данных в сетях. Ставится в конце блока данных, будет равен 1, если в основном сообщении нечетное число единиц, и равен 0, если сообщение с четным числом единиц. Применяется для небольших блоков данных. Контрольная сумма – другой метод обнаружения ошибок. Применяются алгоритмы CRC, хэш-функции. Если конт. сумма не совпадает то произошла ошибка.
назад
3 доп теория
- Помехоустойчивый код – код, который позволяет исправлять ошибки, если их кол-во не превышает некоторого уровня.
- Расстояние Хэмминга – кол-во позиций, в которых различаются два закодированных сообщения одинаковой длины.
- Код Хэмминга — самоконтролирующийся и самокорректирующийся код. Построен применительно к двоичной системе счисления. Позволяет исправлять одиночную ошибку и находить двойную.
…