input output management in operating systems

https://docs.google.com/document/d/101-0przksB45m6JVsa3UM5iB2CBCUYZMwgowYeisb98/edit

COMPARATORS

Unit-V

COMBINATIONAL LOGIC DESIGN

Comparators

Comparing two binary words for equality is a commonly used operation in computer systems and device interfaces. A circuit that compares two binary words and indicates whether they are equal is called a comparator.

Some comparators interpret their input words as signed or unsigned numbers and also indicate an arithmetic relationship (greater or less than) between the words. These devices are often called magnitude comparators.

Comparator Structure

EXCLUSIVE OR and EXCLUSIVE NOR gates may be viewed as 1-bit comparators. Figure 1(a) shows an interpretation of the 74x86 XOR gate as a 1-bit comparator. The active-high output, DIFF, is asserted if the inputs are different. The outputs of four XOR gates are ORed to create a 4-bit comparator in (b). The DIFF output is asserted if any of the input-bit pairs are different. Given enough XOR gates and wide enough OR gates, comparators with any number of input bits can be built.

Figure 1: Comparators using 74x86 (a) 1-bit Comparator (b) 4-bit Comparator

Iterative Circuits

An iterative circuit is a special type of combinational circuit as shown in Figure 2. The circuit contains n identical modules, each of which has both primary inputs and outputs and cascading inputs and outputs. The leftmost cascading inputs are called boundary inputs and are connected to fixed logic values in most iterative circuits. The rightmost cascading outputs are called boundary outputs and usually provide important information.

Iterative circuits are well suited to problems that can be solved by a simple iterative algorithm:

1. Set C0 to its initial value and set i to 0.

2. Use Ci and PIi to determine the values of POi and Ci+1.

3. Increment i.

4. If i < n, go to step 2.

In an iterative circuit, the loop of steps 2–4 is “unwound” by providing a separate combinational circuit that performs step 2 for each value of i.

Figure 2: General Structure of an iterative Combinational Circuit

Eg: The 74x85 4-bit comparator and the 74x283 4-bit adder are examples of MSI circuits that can be used as the individual modules in a larger iterative circuit.

An Iterative Comparator Circuit

Two n-bit values X and Y can be compared one bit at a time using a single bit EQi at each step to keep track of whether all of the bit-pairs have been equal so far:

1. Set EQ0 to 1 and set i to 0.

2. If EQi is 1 and Xi and Yi are equal, set EQ_{i +1} to 1. Else set EQ_i+1 to 0.

3. Increment i.

4. If i < n, go to step 2.

Figure 3: An iterative Comparator Circuit (a) Module for one bit (b) Complete Circuit

Figure 3 shows a corresponding iterative circuit, this circuit has no primary outputs; the boundary output is our interest. Other iterative circuits, such as the ripple adder, have primary outputs of interest. When a choice between the iterative comparator circuit and one of the parallel comparators, then prefer the parallel comparator. The iterative comparator saves little if any cost, and it’s very slow because the cascading signals need time to “ripple” from the leftmost to the rightmost module. Iterative circuits that process more than one bit at a time, using modules like the 74x85 4-bit comparator and 74x283 4-bit adder, are much more likely to be used in practical designs.

Figure 4: Traditional Logic Symbol for the 74x85 4-bit comparator

Behavioral VHDL program for comparing 4-bit integers using 74x85.

library IEEE;

use IEEE.std_logic_1164.all;

use IEEE.std_logic_arith.all;

entity comp74x85 is

port ( A, B: in STD_LOGIC_VECTOR(3 downto 0);

ALTBIN, AGTBIN, AEQBIN: in STD_LOGIC;

ALTBOUT, AGTBOUT, AEQBOUT: out STD_LOGIC);

end comp74x85;

architecture behavior of comp74x85 is

begin

process (A, B, ALTBIN, AGTBIN, AEQBIN)

begin

ALTBIN<= '0'; 

AGTBIN<= '0'; 

AEQBIN<= '0'; 

if A < B then 

ALTBIN <= '1';

AGTBIN<= '0'; 

AEQBIN<= '0'; 

else if A > B then 

ALTBIN<= '0'; 

AGTBIN<= '1'; 

AEQBIN<= '0'; 

else

ALTBIN<= '0'; 

AGTBIN<= '0'; 

AEQBIN<= '1'; 

end if;

end if;

end process;

end behavior;

Standard MSI Comparators

Comparator applications are common enough that several MSI comparators have been developed commercially. The 74x85 is a 4-bit comparator with the logic symbol shown in Figure 4. It provides a greater-than output (AGTBOUT) and a less-than output (ALTBOUT) as well as an equal output (AEQBOUT). The ’85 also has cascading inputs (AGTBIN, ALTBIN, and AEQBIN) for combining multiple ’85s to create comparators for more than four bits. Both the cascading inputs and the outputs are arranged in a 1-out-of-3 code, since in normal operation exactly one input and one output should be asserted.

Figure 5: Traditional Logic Symbol for the 74x682 8-bit Comparator

Behavioral VHDL program for comparing 8-bit integers using 74x682.

library IEEE;

use IEEE.std_logic_1164.all;

use IEEE.std_logic_arith.all;

entity comp74x682 is

port ( P,Q: in STD_LOGIC_VECTOR(7 downto 0);

PEQQ_L, PGTQ_L: out STD_LOGIC);

end comp74x682;

architecture behavior of comp74x682 is

begin

process (P,Q)

begin

if P>Q then 

PGTQ_L <= '0';

PEQQ_L<= '1'; 

else if P = Q then 

PGTQ_L <= '1';

PEQQ_L<= '0'; 

else

PGTQ_L <= '1';

PEQQ_L<= '1'; 

end if;

end if;

end process;

end behavior;

Figure 6: A 12-bit Comparator using 74x85s

Behavioral VHDL program for comparing 12-bit integers using 74x85.

library IEEE;

use IEEE.std_logic_1164.all;

use IEEE.std_logic_arith.all;

entity comp12bit is

port ( XD,YD: in STD_LOGIC_VECTOR(11 downto 0);

XLTY,XEQY,XGTY: out STD_LOGIC);

end comp12bit;

architecture structural of comp74x85 is

signal XLTY4, XEQY4, XGTY4, XLTY8, XGTY8, XEQY8: STD_LOGIC; 

begin

U1: comp74x85 port map(XD[3 downto 0),YD(3 downto 0),'0','0','1',XLTY4,XGTY4,XEQY4);

U2: comp74x85 port map(XD[7 downto 4),YD(7 downto 4),XLTY4,XGTY4,XEQY4,XLTY8,XGTY8,XEQY8);

U3: comp74x85 port map(XD[11 downto 8),YD(11 downto 8),XLTY8,XGTY8,XEQY8,XLTY,XGTY,XEQY);

end structural; 

The cascading inputs are defined so the outputs of an ’85 that compares less-significant bits are connected to the inputs of an ’85 that compares more-significant bits, as shown in Figure 6 for a 12-bit comparator. Each ’85 develops its cascading outputs roughly according to the following pseudo-logic equations:

The parenthesized sub-expressions above are not normal logic expressions, but indicate an arithmetic comparison that occurs between the A3–A0 and B3–B0 inputs. In other words, AGTBOUT is asserted if A > B or if A = B and AGTBIN is asserted (if the higher-order bits are equal, then the lower-order bits are considered). The arithmetic comparisons can be expressed using normal logic expressions, Eg.,

Such expressions must be substituted into the pseudo-logic equations above to obtain genuine logic equations for the comparator outputs. Several 8-bit MSI comparators are also available. The simplest of these is the 74x682, whose logic symbol is shown in Figure 6 and whose internal logic diagram is shown in Figure 7.

Figure 7: Logic Diagram for the 74x682 8-bit comparator including pin numbers for a standard 20-pin dual-in-line package

The top half of the circuit checks the two 8-bit input words for equality. Each XNOR-gate output is asserted if its inputs are equal, and the PEQQ_L output is asserted if all eight input-bit pairs are equal. The bottom half of the circuit compares the input words arithmetically, and asserts /PGTQ if P[7–0] > Q[7–0]. Unlike the 74x85, the 74x682 does not have cascading inputs. Also unlike the ’85, the ’682 does not provide a “less than” output. However, any desired condition, including ≤ and ≥, can be formulated as a function of the PEQQ_L and PGTQ_L outputs, as shown in Figure 8.

Figure 8: Arithmetic Conditions derived from 74x682 Outputs

Behavioral VHDL program for deriving arithmetic conditions from 74x682 Outputs.

library IEEE;

use IEEE.std_logic_1164.all;

use IEEE.std_logic_arith.all;

entity arith74x682 is

port ( P,Q: in STD_LOGIC_VECTOR(7 downto 0);

PNEQ, PEQQ, PGTQ, PGEQ, PLEQ, PLTQ: out STD_LOGIC);

end comp74x682;

architecture stuctural of arith74x682 is

PEQQ_L,PGTQ_L: STD_LOGIC;

begin

U1: comp74x682 port map(P,Q, PEQQ_L, PGTQ_L);

assign PNEQ=PEQQ_L;

--not, nand and and are built-in primitives of VHDL

U2: not portmap(PEQQ,PEQQ_L);

U3: not port map(PGTQ,PGTQ_L);

U4: nand port map(PGEQ,PEQQ_L, PGTQ_L);

assign PLEQ=PGTQ_L;

U5: and port map(PLTQ,PEQQ_L,PGTQ_L);

end structural;

Behavioral VHDL program for comparing 8-bit unsigned integers

library IEEE;

use IEEE.std_logic_1164.all;

entity vc is

port (

A, B: in STD_LOGIC_VECTOR (7 downto 0);

EQ, NE, GT, GE, LT, LE: out STD_LOGIC

);

end vc;

architecture vc_arch of vc is

begin

process (A, B)

begin

EQ <= '0'; NE <= '0'; GT <= '0'; GE <= '0'; LT <= '0'; LE <= '0';

if A = B then EQ <= '1'; end if;

if A /= B then NE <= '1'; end if;

if A > B then GT <= '1'; end if;

if A >= B then GE <= '1'; end if;

if A < B then LT <= '1'; end if;

if A <= B then LE <= '1'; end if;

end process;

end vc_arch

Behavioral VHDL program for comparing 8-bit integers of various types.

library IEEE;

use IEEE.std_logic_1164.all;

use IEEE.std_logic_arith.all;

entity vcmpa is

port (

A, B: in UNSIGNED (7 downto 0);

C: in SIGNED (7 downto 0);

D: in STD_LOGIC_VECTOR (7 downto 0);

A_LT_B, B_GE_C, A_EQ_C, C_NEG, D_BIG, D_NEG: out STD_LOGIC

);

end vcmpa;

architecture vcmpa_arch of vcmpa is

begin

process (A, B, C, D)

begin

A_LT_B <= '0'; B_GE_C <= '0'; A_EQ_C <= '0'; C_NEG <= '0'; D_BIG <= '0'; D_NEG <= '0';

if A < B then A_LT_B <= '1'; end if;

if B >= C then B_GE_C <= '1'; end if;

if A = C then A_EQ_C <= '1'; end if;

if C < 0 then C_NEG <= '1'; end if;

if UNSIGNED(D) > 200 then D_BIG <= '1'; end if;

if SIGNED(D) < 0 then D_NEG <= '1'; end if;

end process;

end vcmpa_arch;

exclusive OR Gates, Parity Circuits and hamming Code

Unit-V

COMBINATIONAL LOGIC DESIGN

Exclusive OR Gates and Parity Circuits

An Exclusive OR (XOR) gate is a 2-input gate whose output is 1 if exactly one of its inputs is 1. Stated another way, an XOR gate produces a 1 output if its inputs are different. An Exclusive NOR (XNOR) or Equivalence gate is just the opposite—it produces a 1 output if its inputs are the same. The corresponding truth table for these functions is shown in Table 1.

Table 1: Truth Table for XOR and XNOR functions

The XOR operation is sometimes denoted by the symbol “Å”, that is,

Although EXCLUSIVE OR is not one of the basic functions of switching algebra, discrete XOR gates are fairly commonly used in practice. Most switching technologies cannot perform the XOR function directly; instead, they use multi-gate designs like the ones shown in Figure 1.

Figure1: Multigate designs for the 2-input XOR function (a) AND-OR (b) Three-level NAND

Figure 2: Equivalent Symbol for (a) XOR Gates (b) XNOR Gates

The logic symbols for XOR and XNOR functions are shown in Figure 2. There are four equivalent symbols for each function. All of these alternatives are a consequence of a simple rule:

• Any two signals (inputs or output) of an XOR or XNOR gate may be complemented without changing the resulting logic function.

In bubble-to-bubble logic design, we choose the symbol that is most expressive

of the logic function being performed.

Four XOR gates are provided in a single 14-pin SSI IC, the 74x86 shown in Figure 3. New SSI logic families do not offer XNOR gates, although they are readily available in FPGA and ASIC libraries and as primitives in HDLs.

Figure 3: Pin outs of the 74x86 quadruple 2-input Exclusive OR Gate

Parity Circuits

As shown in Figure 4, n XOR gates may be cascaded to form a circuit with n+1 inputs and a single output. This is called an odd-parity circuit, because its output is 1 if an odd number of its inputs are 1. The circuit in (b) is also an odd parity circuit, but it’s faster because its gates are arranged in a tree-like structure. If the output of either circuit is inverted, we get an even-parity circuit, whose output is 1 if even numbers of its inputs are 1.

Figure 4: Cascading XOR gates (a) Daisy-Chain Connection (b) Tree Structure

The 74x280 9-Bit Parity Generator

Rather than build a multibit parity circuit with discrete XOR gates, it is more economical to put all of the XORs in a single MSI package with just the primary inputs and outputs available at the external pins. The 74x280 9-bit parity generator, shown in Figure 5, is such a device. It has nine inputs and two outputs that indicate whether an even or odd number of inputs are 1.

Figure 5: The 74x280 9-bit odd/even parity generator (a) Logic Diagram including pin numbers for a standard 16-pin dual-in-line package (b) traditional logic symbol

VHDL Program

--Behavior Model

library IEEE;

use IEEE.std_logic_1164.all;

entity parity74x280 is

port ( I: in STD_LOGIC_VECTOR (1 to 9);

EVEN, ODD: out STD_LOGIC);

end parity9;

architecture behavior of parity74x280 is

begin

process (I)

variable p : STD_LOGIC;

variable j : INTEGER;

begin

p := I(1);

for j in 2 to 9 loop

if I(j) = '1' then p := not p; end if;

end loop;

ODD <= p;

EVEN <= not p;

end process;

end behavior;

--Structural Model

library IEEE;

use IEEE.std_logic_1164.all;

entity parity74x280 is

port (I: in STD_LOGIC_VECTOR (1 to 9);

EVEN, ODD: out STD_LOGIC);

end parity74x280;

architecture structural of parity74x280 is

component vxor3

port (A, B, C: in STD_LOGIC; Y: out STD_LOGIC);

end component;

signal Y1, Y2, Y3, Y3N: STD_LOGIC;

begin

U1: vxor3 port map (I(1), I(2), I(3), Y1);

U2: vxor3 port map (I(4), I(5), I(6), Y2);

U3: vxor3 port map (I(7), I(8), I(9), Y3);

Y3N <= not Y3;

U4: vxor3 port map (Y1, Y2, Y3, ODD);

U5: vxor3 port map (Y1, Y2, Y3N, EVEN);

end Structural;

Parity-Checking Applications

Error-detecting codes that use an extra bit, called a parity bit, are used to detect errors in the transmission and storage of data. In an even parity code, the parity bit is chosen so that the total number of 1 bits in a code word is even. Parity circuits like the 74x280 are used both to generate the correct value of the parity bit when a code word is stored or transmitted, and to check the parity bit when a code word is retrieved or received.

3 Bit String	Parity Bit
000	0
001	1
010	1
011	0
100	1
101	0
110	0
111	1

Figure 6: Parity generation and checking for an 8-bit-wide memory system

Figure 6 shows how a parity circuit might be used to detect errors in the memory of a microprocessor system. The memory stores 8-bit bytes, plus a parity bit for each byte. The microprocessor uses a bidirectional bus D[0:7] to transfer data to and from the memory. Two control lines, RD and WR, are used to indicate whether a read or write operation is desired, and an ERROR signal is asserted to indicate parity errors during read operations.

To store a byte into the memory chips, we specify an address (not shown), place the byte on D[0–7], generate its parity bit on PIN, and assert WR. The AND gate on the I input of the 74x280 ensures that I is 0 except during read operations, so that during writes the ’280’s output depends only on the parity of the D-bus data. The ’280’s ODD output is connected to PIN, so that the total number of 1s stored is even.

To retrieve a byte, we specify an address (not shown) and assert RD; the byte value appears on DOUT[0–7] and its parity appears on POUT. A 74x541 drives the byte onto the D bus, and the ’280 checks its parity. If the parity of the 9-bit word DOUT[0–7],POUT is odd during a read, the ERROR signal is asserted.

Parity circuits are also used with error-correcting codes such as the Hamming codes. We can correct errors in hamming code as shown in Figure 7. A 7-bit word, possibly containing an error, is presented on DU[1–7]. Three 74x280s compute the parity of the three bit-groups defined by the parity-check matrix.

The outputs of the ’280s form the syndrome, which is the number of the erroneous input bit, if any. A 74x138 is used to decode the syndrome. If the syndrome is zero, the NOERROR_L signal is asserted (this signal also could be named ERROR). Otherwise, the erroneous bit is corrected by complementing it. The corrected code word appears on the DC_L bus.

Note: The active-low outputs of the ’138 led us to use an active-low DC_L bus. If we required an active-high DC bus, we could have put a discrete inverter on each XOR input or output, or used a decoder with active-high outputs, or used XNOR gates.

Figure 7: Error-Correcting Circuit for a 7-bit Hamming Code

VHDL Program

--structural model

library IEEE;

use IEEE.std_logic_1164.all;

use IEEE.std_logic_unsigned.all;

entity hamcorr is

port (DU: IN STD_LOGIC_VECTOR (1 to 7);

DC_L: OUT STD_LOGIC_VECTOR (1 to 7);

NOERROR_L: OUT STD_LOGIC);

end hamcorr;

Architecture structural of hamcorr is

Component parity9 is

port ( I: in STD_LOGIC_VECTOR (1 to 9);

EVEN, ODD: out STD_LOGIC );

End component;

Component dec74x138 is

Port(G1,G2A_L,G2B_L: in std_logic;

A: in std_logic_vector(2 downto 0);

Y_L: out std_logic_vector(7 downto 0));

End component;

Component xor2 is

Port( a,b: in std_logic;

C:out std_logic);

End component;

Signal SYN,EVEN: std_logic_vector(2 downto 0);

Signal E_L: std_logic_vector(7 downto 0);

Begin

U1: parity9 port map(D(1),D(3),D(5),D(7),’0’,’0’,’0’,’0’,’0’, EVEN(0), SYN(0));

U2: parity9 port map(D(2),D(3),D(6),D(7),’0’,’0’,’0’,’0’,’0 ’, EVEN(1), SYN(1));

U3: parity9 port map(D(4),D(5),D(6),D(7),’0’,’0’,’0’,’0’,’0 ’, EVEN(2), SYN(2));

U4: dec74x138 port map(‘1’,’0’,’0’,SYN,NOERROR_L,E_L);

U5:xor2 port map(DU(1), E_L(1),DC_L(1));

U6:xor2 port map(DU(2), E_L(2),DC_L(2));

U7:xor2 port map(DU(3), E_L(3),DC_L(3));

U8:xor2 port map(DU(4), E_L(4),DC_L(4));

U9:xor2 port map(DU(5), E_L(5),DC_L(5));

U10:xor2 port map(DU(6), E_L(6),DC_L(6));

U11:xor2 port map(DU(7), E_L(7),DC_L(7));

End structural;

--Behavioral model

library IEEE;

use IEEE.std_logic_1164.all;

use IEEE.std_logic_unsigned.all;

entity hamcorr is

port (DU: IN STD_LOGIC_VECTOR (1 to 7);

DC: OUT STD_LOGIC_VECTOR (1 to 7);

NOERROR: OUT STD_LOGIC);

end hamcorr;

Architecture behavior of hamcorr is

function syndrome (D: STD_LOGIC_VECTOR)

return STD_LOGIC_VECTOR is

variable SYN: STD_LOGIC_VECTOR (2 downto 0);

begin

SYN(0) := D(1) xor D(3) xor D(5) xor D(7);

SYN(1) := D(2) xor D(3) xor D(6) xor D(7);

SYN(2) := D(4) xor D(5) xor D(6) xor D(7);

return(SYN);

end syndrome;

begin

process (DU)

variable SYN: STD_LOGIC_VECTOR (2 downto 0);

variable i: INTEGER;

begin

DC <= DU;

i := CONV_INTEGER(syndrome(DU));

if i = 0 then NOERROR <= '1';

else NOERROR <= '0'; DC(i) <= not DU(i); end if;

end process;

End  behavior;