Detail Architecture of 8051

Description

1. Oscillator and clock generator:

All operations in a microcontroller are synchronized by the help of an oscillator clock. The oscillator clock generates the clock pulses by which all internal operations are synchronized. A resonant network connected through pins XTAL1 and XTAL2 forms up an oscillator. For this purpose a quartz crystal and capacitors are employed. The crystal run at specified maximum and minimum frequencies typically at 1 MHz to 16 MHz. 2. ALU:

It is 8 bit unit. It performs arithmetic operation as addition, subtraction, multiplication, division, increment and decrement. It performs logical operations like AND, OR and EX-OR. It manipulates 8 bit and 16 bit data. It calculates address of jump locations in relative branch instruction. It performs compare, rotate and compliment operations. It consists of Boolean processor which performs bit, set, test, clear and compliment. 8051 micro controller contains 34 general purpose registers or working registers.2 of them are called math registers A & B and 32 are bank of registers. a. Accumulator(A-reg):

It is 8 bit register. Its address is E0H and it is bit and byte accessible. Result of arithmetic & logic operations performed by ALU is accumulated by this register. Therefore it is called accumulator register. It is used to store 8 bit data and to hold one of operand of ALU units during arithmetical and logical operations. Most of the instructions are carried out on accumulator data. It is most versatile of 2 CPU registers. b. B-register:

It is special 8 bit math register. It is bit and byte accessible. It is used in conjunction with A register as I/P operand for ALU. It is used as general purpose register to store 8 bit data. c. PSW:

It is 8 bit register. Its address is D0H and It is bit and byte accessible. It has 4 conditional flags or math flags which sets or resets according to condition of result. It has 3 control flags, by setting or resetting bit required operation or function can be achieved. The format of flag register is as shown below:

i. MATH FLAG:

1. Carry Flag(CY):

During addition and subtraction any carry or borrow is generated then carry flag is set otherwise carry flag resets. It is used in arithmetic, logical, jump, rotate and Boolean operations.

2. Auxiliary carry flag(AC):

If during addition and subtraction any carry or borrow is generated from lower 4 bit to higher 4 bit then AC sets else it resets. It is used in BCD arithmetic operations.

3. Overflow flag(OV):

If in signed arithmetic operations result exceeds more than 7 bit than OV flag sets else resets.It is used in signed arithmetic operations only.

4. Parity flag(P):

If in result, even no. Of ones “1” are present than it is called even parity and parity flag sets. In result odd no. Of ones “1”are present than it is called odd parity and parity flag resets.

ii. CONTROL FLAGS:

1. FO:

It is user defined flag. The user defines the function of this flag. The user can set ,test n clear this flag through software.

2. RS1 and RS0:

These flags are used to select bank of register by resetting those flags which are as shown in table :

3.Program counter(PC):

The Program Counter (PC) is a 2-byte address which tells the 8051 where the next instruction to execute is found in memory. It is used to hold 16 bit address of internal RAM, external RAM or external ROM locations. When the 8051 is initialized PC always starts at 0000h and is incremented each time an instruction is executed. It is important to note that PC isnt always incremented by one and never decremented.

4. Data pointer register(DTPR):

It is a 16 bit register used to hold address of external or internal RAM where data is stored or result is to be stored. It is used to store 16 bit data. It is divided into2- 8bit registers, DPH-data pointer higher order (83H) and DPL-data pointer lower order (82H). Each register can be used as general purpose register to store 8 bit data and can also be used as memory location. DPTR does not have single internal address. It functions as Base register in base relative addressing mode and in-direct jump.

5. Stack pointer(SP):

It is 8-bit register. It is byte addressable. Its address is 81H. It is used to hold the internal RAM memory location addresses which are used as stack memory. When the data is to be placed on stack by push instruction, the content of stack pointer is incremented by 1, and when data is retrieved from stack, content of stack of stack pointer is decremented by 1.

iii. Special function Registers(SFR): The 8051 microcontroller has 11 SFR divided in 4 groups: A. Timer/Counter register: 8051 microcontroller has 2-16 bit Timer/counter registers called Timer-reg-T0 And Timer/counter Reg-T1.Each register is 16 bit register divide into lower and higher byte register as shown below: These register are used to hold initial no. of count. All of the 4 register are byte addressable.

1. Timer control register:

8051 microcontroller has two 8-bit timer control register i.e. TMOD and TCON register. TMOD Register: it is 8-bit register. Its address is 89H. It is byte addressable. It used to select mode and control operation of time by writing control word.

2. TCON register:

It is 8-bit register. Its address is 88H. It is byte addressable. Its MSB 4-bit are used to control operation of timer/ counter and LSB 4-bit are used for external interrupt control.

B. Serial data register: 8051 micro controller has 2 serial data register viz. SBUF and SCON.

1. Serial buffer register (SBUF):

it is 8-bit register. It is byte addressable .Its address is 99H. It is used to hold data which is to be transferred serially.

2. Serial control register (SCON):

it is 8-bit register. It is bit/byte addressable. Its address is 98H. The 8-bit loaded into this register controls the operation of serial communication.

C. Interrupt register: 8051 µC has 2 8-bit interrupt register.

1. Interrupt enable register (IE):

it is 8-bit register. It is bit/byte addressable. Its address is A8H.it is used to enable and disable function of interrupt.

2. Interrupt priority register (IP):

It is 8-bit register. It is bit/byte addressable. Its address is B8H. it is used to select low or high level priority of each individual interrupts.

D. Power control register (PCON): it is 8-bit register. It is byte addressable .Its address is 87H. its bits are used to control mode of power saving circuit, either idle or power down mode and also one bit is used to modify baud rate of serial communication.

Internal RAM

Internal RAM has memory 128-byte. See 8051 hardware for further internal RAM design. Internal RAM is organized into three distinct areas: 32 bytes working registers from address 00h to 1Fh 16 bytes bit addressable occupies RAM byte address 20h to 2Fh, altogether 128 addressable bits General purpose RAM from 30h to 7Fh.

Internal ROM

Data memory and program code memory both are in different physical memory but both have the same addresses. An internal ROM occupied addresses from 0000h to 0FFFh. PC addresses program codes from 0000h to 0FFFh. Program addresses higher than 0FFFh that exceed the internal ROM capacity will cause 8051 architecture to fetch codes bytes from external program memory.

• Concept Of hashing• Need of Hashing• Hash Collision• Dealing with Hash Collision• Resolving Hash Collisions by Open Addressing• Primary clustering• Double Rehash
• 2. Concept Of hashing• Hashing: hashing is a technique for performing almost constant time in case of insertion deletion and find operation.• taking a very simple example, as array with its index as key is the example of table.• So each index (key) can be used for accessing values in the constant search time.• Mapping key must be simple to compute and must help in identifying the associated records.• Function that help us in generating such type of keys is termed as Hash Function.
• 3. Hashing• let h(key) is hashing function that returns the hash code. h(key) = key%1000, which can produce any value between 0 and 999. as shown in figure:
• 4. Need of Hashing• Hashing maps large data sets of variable length to smaller data sets of a fixed length. For example, an inventory file of a company having more than 100 items and the key to each record is a seven digit part number. To use direct indexing using entire seven digit key, an array of 10 million elements would be required. Which clearly is wastage of space, since company is unlikely to stock more than few thousand parts.• Hence hashing provides an alternative to convert seven digit key into an integer within limited range. The values returned by a hash function are called hash values, hash codes.
• 5. • Suppose two keys k1 and k2 hashes such that h(k1) = h(k2). Here two keys hashes into the same value and are supposed to occupy same slot in hash table ,which is unacceptable.• Such a situation is termed as hash collision.
• 6. Dealing with Hash Collision• Two methods to deal with hash collision are:• Rehashing and Chaining Rehashing: invokes a secondary hash function (say Rh(key)), which is applied successively until an empty slot is found, where a record can be placed. Chaining: builds a Linked list of items whose key hashes to same value. During search this short linked list is traversed sequentially for the desired key. This technique requires extra link field to each table position.
• 7. hashingAnalysis:• The worst case running time for insertion is O(1).• Deletion of an element x can be accomplished in O(1) time if the lists are doubly linked.• In the worst case behaviour of chain-hashing, all n keys hash to the same slot, creating a list of length n. The worst-case time for search is thus θ(n) plus the time to compute the hash function.
• 8. A good hash function is one that minimizes collision and spreads the records uniformly throughout the table. that is why it is desirable to have larger array size than actual number of records. More formally, suppose we want to store a set of size n in a table of size m. The ratio α = n/m is called a load factor, that is, the average number of elements stored in a Table.

• 1. Prims Algorithm on minimum spanning tree
• 2. What is Minimum Spanning Tree?• Given a connected, undirected graph, a spanning tree of that graph is a subgraph which is a tree and connects all the vertices together.• A single graph can have many different spanning trees.• A minimum spanning tree is then a spanning tree with weight less than or equal to the weight of every other spanning tree.
• 3. graph GSpanning Tree from Graph G2 2 4 3 4 51 1 1
• 4. Algorithm for finding Minimum Spanning Tree• The Prims Algorithm• Kruskals Algorithm• Baruvkas Algorithm
• 5. About Prim’s AlgorithmThe algorithm was discovered in 1930 bymathematician Vojtech Jarnik and later independentlyby computer scientist Robert C. Prim in 1957.The algorithm continuously increases the size of atree starting with a single vertex until it spans all thevertices. Prims algorithm is faster on densegraphs.Prims algorithm runs in O(n*n)But the running time can be reduceusing a simple binary heap data structureand an adjacency list representation
• 6. • Prims algorithm for finding a minimal spanning tree parallels closely the depth- and breadth-first traversal algorithms. Just as these algorithms maintained a closed list of nodes and the paths leading to them, Prims algorithm maintains a closed list of nodes and the edges that link them into the minimal spanning tree.• Whereas the depth-first algorithm used a stack as its data structure to maintain the list of open nodes and the breadth-first traversal used a queue, Prims uses a priority queue.
• 7. Let’s see an example to understand Prim’s Algorithm.
• 8. Lets…. At first we declare an array named: closed list. And consider the open list as a priority queue with min-heap. Adding a node and its edge to the closed list indicates that we have found an edge that links the node into the minimal spanning tree. As a node is added to the closed list, its successors (immediately adjacent nodes) are examined and added to a priority queue of open nodes.
• 9. Total Cost: 0Open List: dClose List:
• 10. Total Cost: 0Open List: a, f, e, bClose List: d
• 11. Total Cost: 5Open List: f, e, bClose List: d, a
• 12. Total Cost: 11Open List: b, e, gClose List: d, a, f
• 13. Total Cost: 18Open List: e, g, cClose List: d, a, f, b
• 14. Total Cost: 25Open List: c, gClose List: d, a, f, b, e
• 15. Total Cost: 30Open List: gClose List: d, a, f, b, e, c
• 16. Total Cost: 39Open List:Close List: d, a, f, b, e, c
• 17. PSEUDO-CODE FOR PRIMS ALGORITHM Designate one node as the start node Add the start node to the priority queue of open nodes. WHILE (there are still nodes to be added to the closed list) { Remove a node from priority queue of open nodes, designate it as current node. IF (the current node is not already in the closed list) { IF the node is not the first node removed from the priority queue, add the minimal edge connecting it with a closed node to the minimal spanning tree. Add the current node to the closed list. FOR each successor of current node IF (the successor is not already in the closed list OR the successor is now connected to a closed node by an edge of lesser weight than before) Add that successor to the priority queue of open nodes; } }
• 18. Sample C++ Implementation• void prim(graph &g, vert s) { • int minvertex(graph &g, int *d) { • int v;• int dist[g.num_nodes];• int vert[g.num_nodes]; • for (i = 0; i < g.num_nodes; i++) • if (g.is_marked(i, UNVISITED)) {• for (int i = 0; i < g.num_nodes; i++) { • v = i; break;• dist[i] = INFINITY; • }• dist[s.number()] = 0; • for (i = 0; i < g.num_nodes; i++) • if ((g.is_marked(i, UNVISITED)) && (dist[i] < dist[v])) v = i;• for (i = 0; i < g.num_nodes; i++) {• vert v = minvertex(g, dist); • return (v); • }• g.mark(v, VISITED);• if (v != s) add_edge_to_MST(vert[v], v);• if (dist[v] == INFINITY) return;• for (edge w = g.first_edge; g.is_edge(w), w = g.next_edge(w)) {• if (dist[g.first_vert(w)] = g.weight(w)) {• dist[g.second_vert(w)] = g.weight(w);• vert[g.second_vert(w)] = v;• }• }• }• }
• 19. Complexity Analysis Minimum edge weight data Time complexity (total) structureadjacency matrix, searching O(V*V)binary heap and adjacency O((V + E) log(V)) = O(Elist log(V))Fibonacci heap and O(E + V log(V))adjacency list
• 20. Application One practical application of a MST would be in the design of a network. For instance, a group of individuals, who are separated by varying distances, wish to be connected together in a telephone network. Because the cost between two terminal is different, if we want to reduce our expenses, Prims Algorithm is a way to solve it Connect all computers in a computer science building using least amount of cable. A less obvious application is that the minimum spanning tree can be used to approximately solve the traveling salesman problem. A convenient formal way of defining this problem is to find the shortest path that visits each point at least once. Another useful application of MST would be finding airline routes. The vertices of the graph would represent cities, and the edges would represent routes between the cities. Obviously, the further one has to travel, the more it will cost, so MST can be applied to optimize airline routes by finding the least costly paths with no cycles.
  
  
  
  

Recovering unallocated space of a USB flash drive.

Today I played with the latest SUSE Linux Live. I had not have a DVD drive and used USB flash drive instead. I wanted to reformat my flash drive, but suddenly found it that it had not been possible. The most of the disk space had been unallocated, and my Windows 8 did not allow me to use it.

Microsoft DiskPart version 6.2.9200
Copyright (C) 1999-2012 Microsoft Corporation.
On computer: COMPUTER
DISKPART> list disk
  Disk ###  Status         Size     Free     Dyn  Gpt
  --------  -------------  -------  -------  ---  ---
  Disk 0    Online          298 GB      0 B
  Disk 1    Online         7509 MB  6619 MB
DISKPART> select disk 1
Disk 1 is now the selected disk.
DISKPART> clean
DiskPart succeeded in cleaning the disk.
DISKPART> create partition primary
DiskPart succeeded in creating the specified partition.
DISKPART> exit