Featured post

Top 5 books to refer for a VHDL beginner

VHDL (VHSIC-HDL, Very High-Speed Integrated Circuit Hardware Description Language) is a hardware description language used in electronic des...

Showing posts with label Tutorial. Show all posts
Showing posts with label Tutorial. Show all posts

Wednesday, 13 May 2015

IEEE Standards

vlsi-ieee802IEEE 802 refers to a family of IEEE standards dealing with local area networks and metropolitan area networks.

More specifically, the IEEE 802 standards are restricted to networks carrying variable-size packets. By contrast, in cell relay networks data is transmitted in short, uniformly sized units called cells. Isochronous networks, where data is transmitted as a steady stream of octets, or groups of octets, at regular time intervals, are also out of the scope of this standard. The number 802 was simply the next free number IEEE could assign, though “802” is sometimes associated with the date the first meeting was held — February 1980.

The services and protocols specified in IEEE 802 map to the lower two layers (Data Link and Physical) of the seven-layer OSI networking reference model. In fact, IEEE 802 splits the OSI Data Link Layer into two sub-layers named Logical Link Control (LLC) and Media Access Control (MAC), so that the layers can be listed like this:

  • Data link layer
  • LLC Sublayer
  • MAC Sublayer
  • Physical layer

The IEEE 802 family of standards is maintained by the IEEE 802 LAN/MAN Standards Committee (LMSC). The most widely used standards are for the Ethernet family, Token Ring, Wireless LAN, Bridging and Virtual Bridged LANs. An individual Working Group provides the focus for each area.

IEEE developed a set of 802 network standards. They include:

  • IEEE 802.1: Standards related to network management.
  • IEEE 802.2: General standard for the data link layer in the OSI Reference Model. The IEEE divides this layer into two sub-layers -- the logical link control (LLC) layer and the media access control (MAC) layer. The MAC layer varies for different network types and is defined by standards IEEE 802.3 through IEEE 802.5.
  • IEEE 802.3: Defines the MAC layer for bus networks that use CSMA/CD. This is the basis of the Ethernet standard.
  • IEEE 802.4: Defines the MAC layer for bus networks that use a token-passing mechanism (token bus networks).
  • IEEE 802.5: Defines the MAC layer for token-ring networks.
  • IEEE 802.6: Standard for Metropolitan Area Networks (MANs).

Tuesday, 12 May 2015

Ethernet–Introduction

VLSI_ETHERNETIn today's business world, reliable and efficient access to information has become an important asset in the quest to achieve a competitive advantage. File cabinets and mountains of papers have given way to computers that store and manage information electronically.

Computer networking technologies are the glue that binds these elements together. Networking allows one computer to send information to and receive information from another. We can classify network technologies as belonging to one of two basic groups. Local area network (LAN) technologies connect many devices that are relatively close to each other, usually in the same building. The library terminals that display book information would connect over a local area network. Wide area network (WAN) technologies connect a smaller number of devices that can be many kilometers apart.

In comparison to WANs, LANs are faster and more reliable, but improvements in technology continue to blur the line of demarcation. Fiber optic cables have allowed LAN
technologies to connect devices tens of kilometers apart, while at the same time greatly
improving the speed and reliability of WANs.

Read More >>

Ethernet

VLSI_ETHERNETEthernet has been a relatively inexpensive, reasonably fast, and very popular LAN technology for several decades. Two individuals at Xerox PARC -- Bob Metcalfe and D.R. Boggs -- developed Ethernet beginning in 1972 and specifications based on this work appeared in IEEE 802.3 in 1980. Ethernet has since become the most popular and most widely deployed network technology in the world. Many of the issues involved with Ethernet are common to many network technologies, and understanding how Ethernet addressed these issues can provide a foundation that will improve your understanding of networking in general.

The Ethernet standard has grown to encompass new technologies as computer networking has matured. Specified in a standard, IEEE 802.3, an Ethernet LAN typically uses coaxial cable or special grades of twisted pair wires. Ethernet is also used in wireless LANs. Ethernet uses the CSMA/CD access method to handle simultaneous demands. The most commonly installed Ethernet systems are called 10BASE-T and provide transmission speeds up to 10 Mbps. Devices are connected to the cable and compete for access using a Carrier Sense Multiple Access with Collision Detection (CSMA/CD) protocol. Fast Ethernet or 100BASE-T provides transmission speeds up to 100 megabits per second and is typically used for LAN backbone systems, supporting workstations with 10BASE-T cards. Gigabit Ethernet provides an even higher level of backbone support at 1000 megabits per second (1 gigabit or 1 billion bits per second). 10-Gigabit Ethernet provides up to 10 billion bits per second.

The Ethernet standard has grown to encompass new technologies as computer networking has matured. Specified in a standard, IEEE 802.3, an Ethernet LAN typically uses coaxial cable or special grades of twisted pair wires. Ethernet is also used in wireless LANs. Ethernet uses the CSMA/CD access method to handle simultaneous demands. The most commonly installed Ethernet systems are called 10BASE-T and provide transmission speeds up to 10 Mbps. Devices are connected to the cable and compete for access using a Carrier Sense Multiple Access with Collision Detection (CSMA/CD) protocol. Fast Ethernet or 100BASE-T provides transmission speeds up to 100 megabits per second and is typically used for LAN backbone systems, supporting workstations with 10BASE-T cards. Gigabit Ethernet provides an even higher level of backbone support at 1000 megabits per second (1 gigabit or 1 billion bits per second). 10-Gigabit Ethernet provides up to 10 billion bits per second.

 

Monday, 25 March 2013

Use SystemVerilog for coverage metrics

The design-and-verification industry is at the intersection of two important trends in the design and verification of SOC (system-on-chip) devices: the adoption of SystemVerilog HDVL (hardware-description and -verification language) and the increasingly critical role for coverage metrics. The interest in System Verilog is understandable; this IEEE-standard language has the features for RTL (register-transfer-level) design, high-level modeling, testbench creation, and assertion specification (Reference).

SystemVerilog also provides constructs for design-and-verification engineers to specify functional coverage points—conditions that designers must exercise for complete verification of the design. Designers increasingly use functional coverage to supplement traditional code coverage. The primary driver for this evolution is the widespread use of constrained-random-stimulus generation.

Traditional verification plans typically include a list of design features or tests that verify features and test status. This approach has worked well with handwritten, directed tests because of the clear correspondence between features and tests. However, verification consists of writing and running each test in simulation, perhaps after turning on some code coverage to help identify features you may have missed in the plan.

Constrained-random-stimulus generation requires a different approach, in which each automatically generated test can exercise many features and parts of the design. A modern verification plan lists features, functional coverage points for the features, and coverage status. You gauge verification closure by the number of coverage points you exercise rather than the number of tests you complete.

SystemVerilog provides all the features necessary to develop both handwritten tests and constrained-random testbenches and to track progress toward closure. Most simulators have built-in code coverage for the new design constructs that SystemVerilog introduces. Thus, code-coverage metrics are available for designs taking advantage of the language's advanced RTL features.

SystemVerilog provides several powerful specification methods for functional coverage. The first is cover property, which is part of the SVA (SystemVerilog Assertions) subset of the language. SVA's assertion features, including temporal sequences, are also available for functional coverage.
For example,

MiniMuM and MaxiMuM response
minimum_response: cover property (@(posedge clk)
(req ##1 ack ));
maximum_response: cover property (@(posedge clk)
(req ##5 ack ));

Above example ensures that the simulator exercises the two extremes—one and five cycles—of a request-acknowledge handshake. Both simulators and many formal-analysis tools support the cover-property construct. If formal analysis can prove that a coverage point is unreachable, a design bug may be blocking important functions from being exercised. If formal analysis instead provides a trace showing how to reach a coverage point, this trace can provide a good hint on how to write or generate a test.

Beyond individual coverage properties, you sometimes must track ranges of values. SystemVerilog provides the cover-group construct, which is not part of SVA, to perform this function.
For example,

PayLoad sizes of incoming Packets
minimum_response: cover property (@(posedge clk)
(req ##1 ack ));
maximum_response: cover property (@(posedge clk)
(req ##5 ack ));
covergroup payloads_seen (@(packet_received);
coverpoint payload_size {
bins empty = { 0 };
bins minimum = { 1 };
bins maximum= { 1023 };
bins others = default; }
endgroup : payloads_seen

Above example tracks the payload sizes of incoming packets on a network interface and ensures the coverage of corner cases of empty, minimum, and maximum payloads. SystemVerilog also provides the cross construct to measure cross-coverage between two coverage points. This feature allows the tracking of combinations of coverage metrics.
For example,

EnumEratEd typE for four packEt cLassEs

enum { read, write, atomic, ctrl } packet_class;
covergroup packets_seen (@(packet_received);
coverpoint payload_size {
bins empty = { 0 };
bins minimum = { 1 };
bins maximum= { 1023 };
bins others = default; }
coverpoint packet_class;
cross payload_size, packet_class;
endgroup : packets_seen

Above example specifies an enumerated type for four packet classes for the network interface, adds a cover point to track the packet classes, and crosses the packet types with the payload sizes.

Ultimately, the SOC-tapeout decision must take into account all coverage metrics. Although functional coverage is the primary method, code coverage has value as a backup to identify areas of the design with no functional coverage due to an incomplete verification plan. The project team needs to merge together code- and functional-coverage results to assess verification progress and help determine verification closure. Coverage is critical for modern, constrained-random verification. Without effective metrics, no reliable way exists to gauge status and manage progress. In addition to its other features and benefits, SystemVerilog provides support for functional coverage. By including coverage in the verification plan from the start of the project and taking advantage of SystemVerilog, the SOC team can employ a complete plan-to-closure methodology that greatly increases the chances for a successful product.

Friday, 15 March 2013

SystemVerilog Event Regions, Race Avoidance & Guidelines

Understanding SystemVerilog event regions  and fundamental coding guidelines can help eliminate race conditions from SystemVerilog designs, testbenches and the interaction between the design and the enhanced SystemVerilog Hardware Verification Language (HVL).

New SystemVerilog event regions have been added to help eliminate race conditions that could occur between design modules and verification environments.

This paper details common verification strategies and how the new event regions facilitate construction of race-free testbenches using new SystemVerilog capabilities. An in-depth explanation of SystemVerilog event regions is included to help understand how race-reduction goals have been met. Important  design & testbench coding guidelines are also included.

SystemVerilog Event Regions, Race Avoidance & Guidelines

Monday, 21 January 2013

SystemVerilog Modports

Modports in SystemVerilog are used to restrict interface access within a interface. The keyword modport indicates that the directions are declared as if inside the module.

Modports can have

  • input : Ports that need to be input.
  • output : Ports that need to be output.
  • inout : Ports that need to be inout
  • ref : Ports that need to be ref.

Few of the examples usages of modports are, we can have interface file for

memory controller where, we can have

  • Modports for memory
  • Modports for system side
  • Modports for testbench

Adding modports to an interface does not require that any of the modports be used when the interface is used. If no modport is specified in the module header or in the port connection, then all the nets and variables in the interface are accessible with direction inout or ref, Below example shows this in greater detail.

 //+++++++++++++++++++++++++++++++++++++++++++++++++
// Define the interface
//+++++++++++++++++++++++++++++++++++++++++++++++++
interface mem_if (input wire clk);
logic reset;
logic we_sys;
logic cmd_valid_sys;
logic ready_sys;
logic [7:0] data_sys;
logic [7:0] addr_sys;
logic we_mem;
logic ce_mem;
logic [7:0] datao_mem;
logic [7:0] datai_mem;
logic [7:0] addr_mem;
//=================================================
//
Modport for System interface
//=================================================
modport system (input clk,reset,we_sys, cmd_valid_sys,
addr_sys, datao_mem,
output we_mem, ce_mem, addr_mem,
datai_mem, ready_sys, ref data_sys);
//=================================================
// Modport for memory interface
//=================================================
modport memory (input clk,reset,we_mem, ce_mem,
addr_mem, datai_mem, output datao_mem);
//=================================================
// Modport for testbench
//=================================================
modport tb (input clk, ready_sys,
output reset,we_sys, cmd_valid_sys, addr_sys,
ref data_sys);

endinterface

//+++++++++++++++++++++++++++++++++++++++++++++++++
// Memory Model
//+++++++++++++++++++++++++++++++++++++++++++++++++
module memory_model (mem_if.memory mif);
// Memory array
logic [7:0] mem [0:255];

//=================================================
// Write Logic
//=================================================
always @ (posedge mif.clk)
if (mif.ce_mem && mif.we_mem) begin
mem[mif.addr_mem] <= mif.datai_mem;
end

//=================================================
// Read Logic
//=================================================
always @ (posedge mif.clk)
if (mif.ce_mem && ~mif.we_mem) begin
mif.datao_mem <= mem[mif.addr_mem];
end

endmodule

//+++++++++++++++++++++++++++++++++++++++++++++++++
// Memory Controller
//+++++++++++++++++++++++++++++++++++++++++++++++++
module memory_ctrl (mem_if.system sif);

typedef enum {IDLE,WRITE,READ,DONE} fsm_t;

fsm_t state;

always @ (posedge sif.clk)
if (sif.reset) begin
state <= IDLE;
sif.ready_sys <= 0;
sif.we_mem <= 0;
sif.ce_mem <= 0;
sif.addr_mem <= 0;
sif.datai_mem <= 0;
sif.data_sys <= 8'bz;
end else begin
case(state)
IDLE : begin
sif.ready_sys <= 1'b0;
if (sif.cmd_valid_sys && sif.we_sys) begin
sif.addr_mem <= sif.addr_sys;
sif.datai_mem <= sif.data_sys;
sif.we_mem <= 1'b1;
sif.ce_mem <= 1'b1;
state <= WRITE;
end
if (sif.cmd_valid_sys && ~sif.we_sys) begin
sif.addr_mem <= sif.addr_sys;
sif.datai_mem <= sif.data_sys;
sif.we_mem <= 1'b0;
sif.ce_mem <= 1'b1;
state <= READ;
end
end
WRITE : begin
sif.ready_sys <= 1'b1;
if (~sif.cmd_valid_sys) begin
sif.addr_mem <= 8'b0;
sif.datai_mem <= 8'b0;
sif.we_mem <= 1'b0;
sif.ce_mem <= 1'b0;
state <= IDLE;
end
end
READ : begin
sif.ready_sys <= 1'b1;
sif.data_sys <= sif.datao_mem;
if (~sif.cmd_valid_sys) begin
sif.addr_mem <= 8'b0;
sif.datai_mem <= 8'b0;
sif.we_mem <= 1'b0;
sif.ce_mem <= 1'b0;
sif.ready_sys <= 1'b1;
state <= IDLE;
sif.data_sys <= 8'bz;
end
end
endcase
end

endmodule

//+++++++++++++++++++++++++++++++++++++++++++++++++
// Test program
//+++++++++++++++++++++++++++++++++++++++++++++++++
program test(mem_if.tb tif);

initial begin
tif.reset <= 1;
tif.we_sys <= 0;
tif.cmd_valid_sys <= 0;
tif.addr_sys <= 0;
tif.data_sys <= 8'bz;
#100 tif.reset <= 0;
for (int i = 0; i < 4; i ++) begin
@ (posedge tif.clk);
tif.addr_sys <= i;
tif.data_sys <= $random;
tif.cmd_valid_sys <= 1;
tif.we_sys <= 1;
@ (posedge tif.ready_sys);
$display("@%0dns Writing address %0d with data %0x",
$time, i,tif.data_sys);
@ (posedge tif.clk);
tif.addr_sys <= 0;
tif.data_sys <= 8'bz;
tif.cmd_valid_sys <= 0;
tif.we_sys <= 0;
end
repeat (10) @ (posedge tif.clk);
for (int i= 0; i < 4; i ++) begin
@ (posedge tif.clk);
tif.addr_sys <= i;
tif.cmd_valid_sys <= 1;
tif.we_sys <= 0;
@ (posedge tif.ready_sys);
@ (posedge tif.clk);
$display("@%0dns Reading address %0d, Got data %0x",
$time, i,tif.data_sys);
tif.addr_sys <= 0;
tif.cmd_valid_sys <= 0;
end
#10 $finish;
end

endprogram

//+++++++++++++++++++++++++++++++++++++++++++++++++
// Testbench
//+++++++++++++++++++++++++++++++++++++++++++++++++
module interface_modports();

logic clk = 0;
always #10 clk++;
//=================================================
// Instianciate Interface and DUT
//=================================================
mem_if miff(clk);
memory_ctrl U_ctrl(miff);
memory_model U_model(miff);
test U_test(miff);

endmodule

You could download file interface_modports.sv here

 


Simulation Result : Modport

 @150ns Writing address 0 with data 24
@230ns Writing address 1 with data 81
@310ns Writing address 2 with data 9
@390ns Writing address 3 with data 63
@690ns Reading address 0, Got data 24
@770ns Reading address 1, Got data 81
@850ns Reading address 2, Got data 9
@930ns Reading address 3, Got data 63








Get free daily email updates!



Follow us!


Wednesday, 5 December 2012

Creating a simple FPGA Project with Xilinx ISE

Xilinx Virtex5 LX300 FPGA chip on the board

We would like to write this post for our friends who wants to create a simple FPGA Project with Xilinx ISE. 

Software

Xilinx ISE as a software package containing a graphical IDE, design entry tools, a simulator, a synthesizer (XST) and implementation tools. Limited version of Xilinx ISE (WebPack) can be downloaded for free from the Xilinx website.

It is not mandatory to use Xilinx software for all tasks (for example, synthesis can be done with Synplify, simulation - with Modelsim etc.), but it is the easier option to start off.

The information in this article applies to Xilinx ISE version 9.2.03i, but other versions (since 8.x) shouldn't be very different. If your version is older than 8.x, you'd better upgrade.

Creating a project

To create a project, start a Project Navigator and select File->New Project. You will be asked for project name and folder. Leave "top-level source type" as HDL.

Now we should choose a target device (we will use a Spartan-3A xc3s50a device as an example) as well as set up some other options:

A dialog of creating project in Xilinx ISE

The Project Navigator window contains a sidebar, which is on the left side by default. The upper part of this sidebar lists all project files, and the lower part lists tasks that are applicable for the file selected in the upper part.

Design Entry

Now, let's add a new source file to our project. We'll start from a simple 8-bit counter, which adds 1 to its value every clock cycle. This counter will have the following ports:

  • CLK - input clock signal;
  • CLR - input asynchronous clear signal (set counter value to 0);
  • DOUT - output counter value (8-bit bus).

We'll define our counter as a VHDL module. VHDL language will be covered in more details in further chapters.

To create a new source file, choose "Create New Source" task and select "VHDL module" source type. The name of our module will becounter.vhd. Then you will be asked which module to associate the testbench with; choose counter.

A dialog of creating a new source file in Xilinx ISE

Let's write the following code in counter.vhd:

library IEEE;
use IEEE.STD_LOGIC_1164.ALL;
use IEEE.STD_LOGIC_ARITH.ALL;
use IEEE.STD_LOGIC_UNSIGNED.ALL;

entity counter is
    Port ( CLK : in  STD_LOGIC;
           CLR : in  STD_LOGIC;
           DOUT : out  STD_LOGIC_VECTOR (7 downto 0));
end counter;

architecture Behavioral of counter is

signal val: std_logic_vector(7 downto 0);

begin

process (CLK,CLR) is
begin
    if CLR='1' then
        val<="00000000";
    elsif rising_edge(CLK) then
        val<=val+1;
    end if;
end process;

DOUT<=val;

end Behavioral;

ISE inserted library and ports declarations automatically, we only need to write an essential part of VHDL description (inside thearchitecture block).

To check VHDL syntax, select "Synthesize - XST => Check Syntax" task for our module.

Simulation

In order to check that our code works as intended, we need to define input signals and check that output signals are correct. It can be done by creating a testbench.

To create a testbench for our counter, select "Create New Source" task, choose "VHDL Test Bench" module type and name it, for instance, counter_tb.vhd.

VHDL test bench is written in VHDL, just like a hardware device description. The difference is that a testbench can utilize some additional language constructs that aren't synthesizable and therefore cannot be used in real hardware (for example wait statements for delay definition).

In order for testbench file to be visible, choose "Behavioral Simulation" in the combobox in the upper part of the sidebar.

ISE automatically generates most of the testbench code, we need only to add our "stimulus":

LIBRARY ieee;
USE ieee.std_logic_1164.ALL;
USE ieee.std_logic_unsigned.all;
USE ieee.numeric_std.ALL;

ENTITY counter_tb_vhd IS
END counter_tb_vhd;

ARCHITECTURE behavior OF counter_tb_vhd IS

    -- Component Declaration for the Unit Under Test (UUT)
    COMPONENT counter
    PORT(
        CLK : IN std_logic;
        CLR : IN std_logic;         
        DOUT : OUT std_logic_vector(7 downto 0)
        );
    END COMPONENT;

    --Inputs
    SIGNAL CLK :  std_logic := '0';
    SIGNAL CLR :  std_logic := '0';

    --Outputs
    SIGNAL DOUT :  std_logic_vector(7 downto 0);

BEGIN

    -- Instantiate the Unit Under Test (UUT)
    uut: counter PORT MAP(
        CLK => CLK,
        CLR => CLR,
        DOUT => DOUT
    );
    -- Clock generation   
    process is
    begin
        CLK<='1';
        wait for 5 ns;
        CLK<='0';
        wait for 5 ns;
    end process;

    tb : PROCESS
    BEGIN

        CLR<='1';
        wait for 100 ns;

        CLR<='0';

        wait; -- will wait forever
    END PROCESS;

END;

We have added the clock generation process (which generates 100MHz frequency clock) and reset stimulus.

Now select a test bench source file and apply "Xilinx ISE Simulator => Simulate Behavioral Model" task. We should get something like this:

Xilinx ISE Simulator window

It can be seen that our counter works properly.

Synthesis

The next step is to convert our VHDL code into a gate-level netlist (represented in the terms of the UNISIM component library, which contains basic primitives). This process is called "synthesis". By default Xilinx ISE uses built-in synthesizer XST (Xilinx Synthesis Technology).

In order to run synthesis, one should select "Synthesis/Implementation" in the combobox in the upper part of the sidebar, select a top-level module and apply a "Synthesize - XST" task. If the code is correct, there shouldn't be any pproblems during the synthesis.

Synthesizer report contains many useful information. There is a maximum frequency estimate in the "timing summary" chapter. One should also pay attention to warnings since they can indicate hidden problems.

After a successful synthesis one can run "View RTL Schematic" task (RTL stands for register transfer level) to view a gate-level schematic produced by a synthesizer:

RTL schematic view in Xilinx ISE

Notice that an RTL schematic in question contains only one primitive: a counter, which is directly an element from the UNISIM library.

Synthesizer output is stored in NGC format.

Implementation
Implementation design flow
  1. Translate - convert NGC netlist (represented in the terms of the UNISIM library) to NGD netlist (represented in the terms of the SIMPRIM library). The difference between these libraries is that UNISIM is intended for behavioral simulation, and SIMPRIM is a physically-oriented library (containing information about delays etc.) This conversion is performed by the program NGDBUILD and is rather straightforward. The main reason for it to be included is to convert netlist generated by different design entry methods (e.g. schematic entry, different synthesizers etc.) into one unified format.
  2. Map is a process of mapping the NGD netlist onto the specific resources of the particular device (logic cells, RAM modules, etc.) This operation is performed by the MAP program with resutls being stored in NCD format. For Virtex-5 MAP also does placement (see below).
  3. Place and route - as can be inferred from its name, this stage is responsible for the layout. It performs placement (logic resources distribution) and routing (connectivity resources distribution). Place and route is performed by a PAR program. For Virtex-5 devices, though, placement is performed by MAP program (and routing still by PAR program). The output of PAR is stored, again, in NCD format.
Implementation Constraints

Constraints are very important during the implementation. They define pin assignments, clocking requirements and other parameters influencing implementation. Constraints are stored in UCF format (user constraints file).

In order to add constraints one need to add a new source (using "Create New Source" task) and choose "Implementation constraints file" source type. UCF file is a text file that can be directly edited by a user, however, simple consraints can be defined with graphical interface.

When a constraints file is selected in the upper part of the sidebar, the specific tasks become available. These include "Create Timing Constraints" and "Assign Package Pins".

For example, if we specify a frequency requirement on CLK as 100 MHz, the corresponding section of the constraints file will be:

NET "CLK" TNM_NET = CLK;
TIMESPEC TS_CLK = PERIOD "CLK" 100 MHz;

When timing requirements are specified in the constraints file, the implementation tools will strive to meet them (and report an error in the case it can't be met).

Package pins constraints must also be set (according to the board layout).

MAP program converts UCF constraints to the PCF format which is later used by PAR.

There are also synthesis constraints stored in XCF files. They are used rarely and shouldn't be confused with implementation constraints.

Programming file generation

After placement and routing, a file should be generated that will be loaded into the FPGA device to program it. This task is performed by a BITGEN program.

The programming file has .bit extension.

The programming file is loaded to the FPGA using iMPACT.

Get free daily email updates!

Follow us!

Sunday, 14 October 2012

Cyclic Redundancy Check - CRC

crc-polynom-generationCRC Example 

Error detection is an important part of communication systems when there is a chance of data getting corrupted. Whether it’s a piece of stored code or a data transmission, you can add a piece of redundant information to validate the data and protect it against corruption. Cyclic redundancy checking is a robust error-checking algorithm, which is commonly used to detect errors either in data transmission or data storage. In this multipart article we explain a few basic principles.

Modulo two arithmetic is simple single-bit binary arithmetic with all carries or borrows ignored. Each digit is considered independently. This article talks about how modulo two addition is equivalent to modulo two subtraction, and can be performed using an exclusive OR operation followed by a brief on Polynomial division where remainder forms the CRC checksum.

For example, we can add two binary numbers X and Y as follows:

10101001 (X) + 00111010 (Y) = 10010011 (Z)

From this example the modulo two addition is equivalent to an exclusive OR operation. What is less obvious is that modulo two subtraction gives the same results as an addition.

From the previous example let’s add X and Z:
10101001 (X) + 10010011 (Z) = 00111010 (Y)

In our previous example we have seen how X + Y = Z therefore Y = Z – X, but the example above shows that Z+X = Y also, hence modulo two addition is equivalent to modulo two subtraction, and can be performed using an exclusive OR operation.

In integer division dividing A by B will result in a quotient Q, and a remainder R. Polynomial division is similar except that when A and B are polynomials, the remainder is a polynomial, whose degree is less than B.

The key point here is that any change to the polynomial A causes a change to the remainder R. This behavior forms the basis of the cyclic redundancy checking.

If we consider a polynomial, whose coefficients are zeros and ones (modulo two), this polynomial can be easily represented by its coefficients as binary powers of two.

In terms of cyclic redundancy calculations, the polynomial A would be the binary message string or data and polynomial B would be the generator polynomial. The remainder R would be the cyclic redundancy checksum. If the data changed or became corrupt, then a different remainder would be calculated.

Although the algorithm for cyclic redundancy calculations looks complicated, it only involves shifting and exclusive OR operations. Using modulo two arithmetic, division is just a shift operation and subtraction is an exclusive OR operation.

Cyclic redundancy calculations can therefore be efficiently implemented in hardware, using a shift register modified with XOR gates. The shift register should have the same number of bits as the degree of the generator polynomial and an XOR gate at each bit, where the generator polynomial coefficient is one.

Augmentation is a technique used to produce a null CRC result, while preserving both the original data and the CRC checksum. In communication systems using cyclic redundancy checking, it would be desirable to obtain a null CRC result for each transmission, as the simplified verification will help to speed up the data handling.

Traditionally, a null CRC result is generated by adding the cyclic redundancy checksum to the data, and calculating the CRC on the new data. While this simplifies the verification, it has the unfortunate side effect of changing the data. Any node receiving the data+CRC result will be able to verify that no corruption has occurred, but will be unable to extract the original data, because the checksum is not known. This can be overcome by transmitting the checksum along with the modified data, but any data-handling advantage gained in the verification process is offset by the additional steps needed to recover the original data.

Augmentation allows the data to be transmitted along with its checksum, and still obtain a null CRC result. As explained before when obtain a null CRC result, the data changes, when the checksum is added. Augmentation avoids this by shifting the data left or augmenting it with a number of zeros, equivalent to the degree of the generator polynomial. When the CRC result for the shifted data is added, both the original data and the checksum are preserved.

In this example, our generator polynomial (x3 + x2 + 1 or 1101) is of degree 3, so the data (0xD6B5) is shifted to the left by three places or augmented by three zeros.
0xD6B5 = 1101011010110101 becomes 0x6B5A8 = 1101011010110101000.

Note that the original data is still present within the augmented data.

0x6B5A8 = 1101011010110101000
Data = D6B5 Augmentation = 000

Calculating the CRC result for the augmented data (0x6B5A8) using our generator polynomial (1101), gives a remainder of 101 (degree 2). If we add this to the augmented data, we get:

0x6B5A8 + 0b101 = 1101011010110101000 + 101
= 1101011010110101101
= 0x6B5AD

As discussed before, calculating the cyclic redundancy checksum for 0x6B5AD will result in a null checksum, simplifying the verification. What is less apparent is that the original data is still preserved intact.

0x6B5AD = 1101011010110101101
Data = D6B5 CRC = 101

The degree of the remainder or cyclic redundancy checksum is always less than the degree of the generator polynomial. By augmenting the data with a number of zeros equivalent to the degree of the generator polynomial, we ensure that the addition of the checksum does not affect the augmented data.

In any communications system using cyclic redundancy checking, the same generator polynomial will be used by both transmitting and receiving nodes to generate checksums and verify data. As the receiving node knows the degree of the generator polynomial, it is a simple task for it to verify the transmission by calculating the checksum and testing for zero, and then extract the data by discarding the last three bits.

Thus augmentation preserves the data, while allowing a null cyclic redundancy checksum for faster verification and data handling.

Get free daily email updates!

Follow us!