Archive

Archive for July, 2014

Quick differences between different types of ROMs


ROM (Read Only Memory)

  • As the name suggests, Once programmed cannot be reprogrammed.
  •  If the data needs to be updated throw away the programmed chip and start over with a new chip.
  • Pros:
  • less costly when produced in huge volumes
  • Robust, power efficient.
  • Cons:
  • slower

PROM (Programmable Read Only Memory)

  • This also can be programmed only once.
  • This is field programmable (ie., can be programmed anywhere).
  • Economical even when produced in small quantities.

EPROM (Electronically Programmable Read Only Memory)

  • Electronically Programmable.
  • Inexpensive per chip.
  • EPROM eraser is not selective, it erases entire chip.
  • To erase it is to be placed under the UV laser for several minutes.
  • Caution: EPROM kept under the UV laser more than required time might over erase the chip making it un-usable.

EEPROM (Electrically erasable programmable read-only memory)

  • The changes for EPROM cannot be made incrementally. For any change it erases whole chip and re-writes.
  • EEPROM can erase the targeted cells through re-writing only required cells. This way it removes this biggest drawback of EPROM.
  • EEPROM can be changed 1 Byte at a time but it is very slow.
  • Flash memory overcomes the the above limitation of slowness.
  • Flash memory erases in terms of blocks of size 512 Bytes thus improving the overall performance.

References:

http://en.wikipedia.org/wiki/EEPROM

http://computer.howstuffworks.com/rom5.htm

http://www.mycomputerscience.net/2010/06/read-only-memory1.html#

Flash and EEPROM programming from Mcirochip

Codechef: Find the largest AND operation result between any two elements of a given array


At first the problem looks very simple and can be solved easily in O(N^2).

#include <iostream>
using namespace std;
 
int main() {
 
	int n;
	cin>>n;
	long data[n] ;
	for(int i = 0; i < n; i++) {
		cin>>data[i];
		
	}
	long max = 0;
	for(int i = 0; i < n - 1; i++) {
		for (int j = i + 1; j < n; j++)
		if (max < (data[i] & data[j]) )
			max = (data[i] & data[j]);
	}
	cout<<max;
	return 0;
} 

But when it comes to huge data sets the solution for finding the maximum between every pair of elements is too much time consuming. A different approach is needed to find it quickly. Here we are reducing the complexity of the algorithm from O(N^2) to merely O(sizeof(long) * 8 * N). This is a good improvement for this algorithm.


#include <iostream>
using namespace std;
 
int main() {
	int n;
	cin>>n;
	long data[n] ;
	for(int i = 0; i < n; i++) {
		cin>>data[i];
	}
	long res = 0;
	int count = 0;
	for(int i = sizeof(long) * 8; i >= 0; i--) {
		count = 0;
		for (int j = 0; j < n; j++) {
			if ((data[j] & (res | (1 << i))) == (res | (1 << i))) {
				count++;
			}
			if (count >= 2) {
				res |= (1 << i);	
				break;
			}
		}
	}
	cout<<res;
	return 0;
}

The above same code can be found here. http://ideone.com/W1LlV0