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;