Moved!
This blog has moved to it’s own add-on domain, http://www.vlsihomepage.com. Please do bookmark it and visit often for updates. As usual, any feedback/suggestions to improve the blog are welcome.
Sphere: Related ContentCyclic Redundancy Check (CRC)
CRC-16 and CRC-32 algorithms are widely used in diverse communication protocols for robustness. The basic idea behind CRC is that the transmitter computes a string of bits called frame check sequence (or checksum) for each frame based on it’s contents and appends it to the end of the message before sending it to the receiver. The receiver then performs a similar computation and checks the checksum for any induced errors.
To detect burst errors (an error burst begins and ends with an error bit while the intermediate bits are correct), polynomial codes are more reliable than parity calculation. Polynomial codes exploit the modulo-2 arithmetic properties of binary numbers (i.e. binary arithmetic operations without any carries).
CRC computation involves appending a string of zeros to the frame equal in number to the number of FCS bits and modulo-2 divide by using a generator polynomial containing one more bit than the FCS to be generated. This division is similar to performing a bit-wise XOR opertation in the frame - the remainder is the checksum (FCS) that is transmitted. Similarly, the receiver divides the received frame using the same polynomial and checks if the remainder is zero. If the remainder is non-zero, the message has been corrupted.
We can cover CRC generation using an example - consider the message 11100110 that needs to be appended with 4-bit FCS using a generator polynomial of 11001. We need to append four 0’s to the message and modulo-2 divide it by generator polynomial.
Checksum computation
At the receiver end, the message 1 1 1 0 0 1 1 0 0 1 1 0 is modulo-2 divided by 1 1 0 0 1 to check if the remainder is zero.
The schematic is shown below for the four bit checksum computation, the FCS shift register is cleared and first octet is parallel-loaded into the parallel-in serial out shift register. This data is now shifted out MSB first and the shifted out data is XORed with X^3 and passed via feedback path to the selected inputs of FCS shift register. After the entire message has been transmitted, the fcs_ctrl changes from 1 -> 0 so that the current contents of FCS register (the remainder) follows the frame contents.
4-bit CRC schematic
Similarly on the Rx side for checking, the data is shifted into the serial-in parallel-out shift register and the serial data is XORed with X^3 and feedback path drives the FCS shift register. Once the entire message is received, the four bits of FCS register are checked to see if they hold 0s.
The choice of generator polynomial is important since it determines the number of errors it detects. A generator polynomial of N bits will detect single-bit, double-bit errors, all error bursts < N and all odd number of bit errors. The CRC-16 algorithm uses the polynomial X^16 + X^15 + X^2 + 1.
Tanenbaum goes into detail of choosing CRC polynomials in Computer Networks.
Sphere: Related ContentEffective Executive by Peter Drucker
Effectiveness must be learned as an executive is paid for being effective asserts Drucker, the management guru. Effectiveness is the ability to get the right things done and is a habit, a complex of practices that have to be acquired. Outlined below are the steps that could make you more effective according to his book
- Record where the time goes (Know thy time) and analyze the executive’s time (pruning of unnecessary activities) - this action alone will make a man more effective. He needs to be able to dispose of time in fairly large chunks for maximum effectiveness. Identify the time wasters which follow from lack of system or foresight. A crisis that recurs a second time is a crisis that must not occur again. The recurrent crisis is simply a symptom of slovenliness and laziness.
- Focus outwards on your contribution to the organization with concern for results rather than efforts and stress on responsibility. Think through who uses your output and what the user needs to know. Focus on contribution supplies four basic requirements of effective human relations : communications, teamwork, self-development and development of others.
- What is the most important contribution I can make to the performance of this organization?
- What self-development do I need? What knowledge and skills do I need to make the contribution and what standards do I have to set myself?
- Making strengths productive - integrate individual purpose and organization needs appropriately. One has a pretty good idea whether one works better in the morning or at night. One knows whether one works best by making a great many drafts or one meticulous session.
- What are the things that I seem to be able to do with relative ease ? To be effective he builds on what he can do and does it the way hr has found out works best. One feeds the opportunities and starves the problems.
- First things first and one thing at a time. Identify priorities by
- Picking future as against the past
- Focus on opportunity rather than on problem
- Choose your own direction
- Aim High, aim for something that will make a difference.
- Effective decision concerns with rational action. Effective decisions do not flow from consensus of facts but from clash and conflict of divergent opinions.