ReggaetonKing

I just finished my first college course as a freshman, I am taking CSE 210 Machine and Assembly Language. So far so easy, 0_o Anyway, the instructor was going over binary digits and such. He was saying that every byte has a 9th bit which is called a 'parity'. And the reason for the partiy is that number of bits that are on in each byte must be always odd, if not the processor forces odd partiy by automatically setting the parity bit on. Says ok to me but why?

Why exactly does the number of bits in a byte that are 'on' have to be odd. I spend two hours wondering about that question and the instructor said he didn't want to go in "complex hardware details, so for now, it just does!". Some one please explain this to me.

__________________
I would love to change the world, but they won't give me the source code!

DaWei

Your instructor is wrong with his statement that "every" byte has 9 bits, one set aside for parity. Many modern memory implementations are 8 bit, with no bits set aside for parity.

Further, correct parity is not always odd; sometimes it's even (for serial modem transmissions one may select parity odd, even, or none, as well as the total number of bits that represent one transmitted byte).

The idea behind a parity bit is that you examine the other 8 bits then set it so that it makes the total number of bits odd (or even). If a byte should happen to come up with the wrong parity, then you know that the memory took a hit (at least at that byte) and is corrupt.

Parity is also not restricted to a single bit. There may be a bit that makes the total number of one's odd, another that makes the total of alternate bits odd, another that makes the total of all the 4th bits odd, and so forth. If you have enough of these you can do not only error detection, but some limited error correction.

You might want to look up Hamming encoding. Hamming's original method required 3 parity bits for every 4 data bits. If you want to get theoretical, you will need to understand some matrix multiplication, modulo-2 arithmetic, etc.

__________________
Abstraction doesn't make it impossible to write bad code; it makes it possible to write superior code.
Contributor's Corner: Grumpy on C++ Exceptions DaWei on Pointers

ReggaetonKing

DaWei, I always look forward to your posts. Thanks a lot!

__________________
I would love to change the world, but they won't give me the source code!

mrynit

interesting topic. i never heard of parity bit

@ReggaetonKing

If you need help on most topics consult wikipedia
http://en.wikipedia.org/wiki/Parity_bit. error correction is mentioned in the first paragraph :p

__________________
i dont know much about programming but i try to help

lectricpharaoh

On a related note, many processors maintain a set of flags that are modified by the result of instruction execution. For example, on 80x86 processors, there is a parity flag that is set or cleared depending on the result of an operation. Likewise, there is a zero flag that is set when the result of an integer subtraction (or compare, which is identical except for not storing the difference) results in zero. These various flags are used in branching constructs. For example, if B is subtracted from A, and the zero flag is set, both A and B are equal. If it is not set, but the carry flag is set, then B must be greater. If neither the zero nor carry flag is set, then B is less than A.

By testing various flags in conditional instructions, such as conditional jumps, you can handle any of the usual semantics. Thus, 'greater than or equal' is true if either the carry or zero flag is set, 'less than or equal' is true so long as the carry flag is not set, and so on.

However, these are processor flags that reflect the outcome of instructions. They are not directly associated with memory, much less specific memory locations. As DaWei says, many modern systems do away with parity RAM, but back in the day, it was relatively common. One reason is perhaps that manufacturing technology has improved, leading to less defective RAM (and thus, the benefit-to-cost ratio is worse). I know that many (most?) modern hard drives will virtualize the disk sectors, and maintain a pool of extra sectors. When the hardware detects a bad sector, it will mark it as such, and substitute one of the sectors from the pool. This process is entirely transparent to software. I wouldn't be surprised if modern memory implemented a similar failsafe. Possibly the best reason for dumping parity schemes is that traditional (single parity bit) setups will miss many errors. Let's say two bits in a byte are bad, and will yield random results when read (put another way, they deterministically fail 50% of the time). A parity bit will detect situations when one bit fails, but when they both fail, it will miss it. Thus, half the memory errors go completely undetected in this situation.

__________________
A man's knowledge is like an expanding sphere, the surface corresponding to the boundary between the known and the unknown. As the sphere grows, so does its surface; the more a man learns, the more he realizes how much he does not know. Hence, the most ignorant man thinks he knows it all. - L. Sprague de Camp

ReggaetonKing

@lectricpharaoh: Good stuff man! This shit is so interesting and I think of computer in a different way.

__________________
I would love to change the world, but they won't give me the source code!