Tagged: LUT Toggle Comment Threads | Keyboard Shortcuts

  • CG 10:24 pm on May 24, 2013 Permalink | Reply
    Tags: BCH code, cyclic code, digital system, , hamming code, , linear block code, LUT, quad tree, reed muller   

    Principles and Analogies of Error Correction Codes 

    I use a very abstract visual way to explain about different error correction algorithms. Here I will over-simplify every algorithm and then use visualizations instead, just to get the principle of how they works, and why.

    Linear Block Code

    In linear block code, every codewords will have n-k bits of redundant checkin part, and k-bits of message.

    Linear Block Code

    The generator matrix would look like this, where there is some identity matrix in it, that later will be used to generate syndrome to identify errors.

    Linear Block Code Table

    Hamming Code
    The picture below shows how to identify error with even parity bits. The bits in black is the message, the bits in green is the parity to make sure that the number of 1 in a circle is even, the bit in red is the error, that later can be identified because the overlapping circle area will show where the error occur.

    Hamming Code Diagram

    The Hamming Code works like shown by the table below, the parity bits (unlike the previous method) are inserted in certain positions (2^0, 2^1, 2^2 and 2^3) to make sure that each of every 4 bits of message is being screened so that later the error can be tracked.

    Hamming Code Table

    Cyclic Code

    This is my favorite. This method use the characteristic of polynomial in GF(2^n). So that identifying errors can be done by divide the codeword with the generator g(x). If the result is not 0, there is an error. Another thing that I like from this method is that every codeword is a shift from previous codeword (that’s why this method called “cyclic”) . So the implementation will be very easy, just shifting here and there (using LFSR), which in hardware implementation, is “costless”.

    Cyclic Code Table

    BCH Code

    This method is a little bit complicated but the point is, to make a matrix H so that this matrix can screen out every bits (that’s why there are 2 rows that are linearly redundant).

    BCH Code
    Reed Muller

    This one is interesting. This method has orders to identify different number of errors. Look at the matrix below. R(1,3) means that the order is 1 and the message length is 3. In Reed Muller, the pattern is obvious. Each vector in the matrix (x1, x2, x3) are used to search the location of error in convergence. Each row will direct the algorithm to a smaller space of error possibility location.
    Reed Muller 1
    For R(2, 3), we have the same number bits of message, which is three, but this time in order 2. Means that the matrix will be expanded and thus, more error can be detected. The part of matrix in yellow is the “basic” vectors, while the green shows the “additional” vectors to help allocating more errors.

    Now look at R(3,3). More rows of the matrix, and more errors to be detected.


    Reed Muller 3

    So oversimplifyingly, I can say that error correction code, in principle, how to encode a message (to be a codeword) to get through a channel (error correction code is in domain channel coding, while data compression is in domain source coding) so that we would be able to make the message reliable (while in source coding, the target is not reliability but efficiency), by making sure that we can locate error and fix it. And the way to decode is like the illustration of quadtree below. The methods will generate matrix, or equations, or mathematical characteristic (polynomial groups etc) to help to narrow down the search space.

    Quadtree
    Quadtree

    Hopefully this article can be useful, I will teach Reed Solomon Code next week, and let’s see if I can add up more things here, or publish a new blogpost.

     
  • CG 9:27 pm on March 4, 2011 Permalink | Reply
    Tags: , LUT, , ,   

    LUT-based multiplier with FSM 

    — FSM for changing input A and B (4bits)
    — that will be input to multiplier
    — CG – March 2011

    library ieee ;
    use ieee.std_logic_1164.all;

    —————————————————–

    entity FSM_CG is
    port(
    clock: in std_logic;
    reset: in std_logic;
    portAA: out std_logic_vector(3 downto 0);
    portBB: out std_logic_vector(3 downto 0);
    portCC: out std_logic_vector(3 downto 0);
    portU: out std_logic_vector(3 downto 0);
    portV: out std_logic_vector(3 downto 0);
    portW: out std_logic_vector(3 downto 0);
    portA: out std_logic_vector(3 downto 0);
    portB: out std_logic_vector(3 downto 0);
    portC: out std_logic_vector(3 downto 0)
    );
    end FSM_CG;

    —————————————————–

    architecture fsm of FSM_CG is
    component LUT_MUL_BR_CG
    port (
    clk0 : in std_logic;
    x, y: in std_logic_vector(3 downto 0);
    z: out std_logic_vector(3 downto 0);
    portu, portv, portw: out std_logic_vector(3 downto 0);
    porta, portb, portc: out std_logic_vector(3 downto 0)
    );
    end component;

    type state_type is (S0, S1, S2, S3, S4);
    signal next_state, current_state: state_type;
    signal A : std_logic_vector(3 downto 0);
    signal B : std_logic_vector(3 downto 0);
    signal C : std_logic_vector(3 downto 0);
    begin
    state_reg: process(clock, reset)
    begin

    if (reset=’1′) then
    current_state <= S0;
    elsif (clock’event and clock=’1′) then
    current_state <= next_state;
    end if;

    end process;

    — cocurrent process#2: combinational logic
    comb_logic: process(current_state, clock)
    begin
    case current_state is

    when S0 =>
    A <= "0111";
    B <= "0000";
    next_state <= S1;
    when S1 =>
    A <= "0111";
    B <= "0011";
    next_state <= S2;
    when S2 =>
    A <= "0100";
    B <= "0011";
    next_state <= S3;
    when S3 =>
    A <= "0101";
    B <= "0101";
    next_state <= S4;
    when S4 =>
    A <= "0100";
    B <= "0101";
    next_state <= S1;
    end case;
    end process;
    portAA <= A;
    portBB <= B;
    portCC <= C;

    lutmulx: LUT_MUL_BR_CG port map(clock, a, b, c, portU, portV, portW, portA, portB, portC);

    end fsm;

     
  • CG 7:21 pm on March 3, 2011 Permalink | Reply
    Tags: clk, clock, , LUT, , ,   

    LUT-based multiplier with no clk 

     
  • CG 11:55 am on March 3, 2011 Permalink | Reply
    Tags: component, , LUT, , ,   

    Implementing LUT-based multiplier as component 

    LUT_MUL_BR_CG.vhdl

    library ieee;
    use ieee.std_logic_1164.all;
    use IEEE.std_logic_arith.all;
    use IEEE.std_logic_unsigned.all;

    entity LUT_MUL_BR_CG is
    port (
    clk0 : in std_logic;
    x, y: in std_logic_vector(3 downto 0);
    z: out std_logic_vector(3 downto 0);
    portu, portv, portw: out std_logic_vector(3 downto 0);
    porta, portb, portc: out std_logic_vector(3 downto 0)
    );
    end LUT_MUL_BR_CG;

    architecture rtl of LUT_MUL_BR_CG is
    component LUT_BR
    port (
    clk : in std_logic;
    a, b: in std_logic_vector(3 downto 0);
    c: out std_logic_vector(3 downto 0);
    porta, portb, portc: out std_logic_vector(3 downto 0)
    );
    end component;

    signal u : std_logic_vector(3 downto 0);
    signal v : std_logic_vector(3 downto 0);
    signal w : std_logic_vector(3 downto 0);
    begin

    u <= x;
    v <= y;
    lutmul: lut_br port map(clk0, u, v, w, porta, portb, portc);
    z <= w;
    portu <= u;
    portv <= v;
    portw <= w; end rtl;

    LUT_BR.vhdl

    library ieee;
    use ieee.std_logic_1164.all;
    use ieee.std_logic_arith.all;
    use ieee.std_logic_unsigned.all;

    entity LUT_BR is
    port (
    clk: in std_logic;
    a, b: in std_logic_vector(3 downto 0);
    c: buffer std_logic_vector(3 downto 0);
    porta, portb, portk, portc: out std_logic_vector(3 downto 0)
    );
    end entity LUT_BR;

    architecture behavioral of LUT_BR is
    component adder_mod_m_CG
    port (
    x, y: in std_logic_vector(3 downto 0);
    addb_sub: in std_logic;
    z: buffer std_logic_vector(3 downto 0)
    );
    end component;

    signal z : std_logic := ‘0’;
    signal i : std_logic_vector(3 downto 0);
    signal j : std_logic_vector(3 downto 0);
    signal k : std_logic_vector(3 downto 0);

    begin
    process(clk)
    begin
    if clk’event and clk = ‘1’ then
    case a is
    when "0001" => i <= "0000";
    when "0010" => i <= "0001";
    when "0011" => i <= "0011";
    when "0100" => i <= "0010";
    when "0101" => i <= "0110";
    when "0110" => i <= "0100";
    when "0111" => i <= "0101";
    when others => i <= "0000";
    end case;
    case b is
    when "0001" => j <= "0000";
    when "0010" => j <= "0001";
    when "0011" => j <= "0011";
    when "0100" => j <= "0010";
    when "0101" => j <= "0110";
    when "0110" => j <= "0100";
    when "0111" => j <= "0101";
    when others => j <= "0000";
    end case;
    case k is
    when "0000" => c <= "0001";
    when "0001" => c <= "0010";
    when "0010" => c <= "0100";
    when "0011" => c <= "0011";
    when "0100" => c <= "0110";
    when "0101" => c <= "0111";
    when "0110" => c <= "0101";
    when others => c <= "0000";
    end case;
    end if;
    end process;
    porta <= a;
    portb <= b;
    portk <= k;
    portc <= c;
    adderku: adder_mod_m_CG port map (i, j, z, k);

    end architecture behavioral;

    add_mod_m_CG.vhdl

    library ieee;
    use ieee.std_logic_1164.all;
    use IEEE.std_logic_arith.all;
    use IEEE.std_logic_unsigned.all;

    entity adder_mod_m_CG is
    port (
    x, y: in std_logic_vector(3 downto 0);
    addb_sub: in std_logic;
    z: out std_logic_vector(3 downto 0)
    );
    end adder_mod_m_CG;

    architecture rtl of adder_mod_m_CG is
    constant M: std_logic_vector(3 downto 0) := conv_std_logic_vector(7, 4);
    signal long_x, xor_y, sum1, long_z1, xor_m, sum2: std_logic_vector(4 downto 0);
    signal c1, c2, sel: std_logic;
    signal z1, z2: std_logic_vector(3 downto 0);

    begin

    long_x <= ‘0’ & x;
    xor_gates1: for i in 0 to 3 generate
    xor_y(i) <= y(i) xor addb_sub;
    end generate;
    xor_y(4) <= ‘0’;
    sum1 <= addb_sub + long_x + xor_y;
    c1 <= sum1(4);
    z1 <= sum1(3 downto 0);
    long_z1 <= ‘0’ & z1;
    xor_gates2: for i in 0 to 3 generate
    xor_m(i) <= m(i) xor not(addb_sub);
    end generate;
    xor_m(4) <= ‘0’;
    sum2 <= not(addb_sub) + long_z1 + xor_m;
    c2 <= sum2(4);
    z2 <= sum2(3 downto 0);
    sel <= (not(addb_sub) and (c1 or c2)) or (addb_sub and not(c1));
    with sel select z <= z1 when ‘0’, z2 when others;

    end rtl;

     
  • CG 3:15 pm on February 25, 2011 Permalink | Reply
    Tags: finite field, look up table, LUT, , ,   

    4 bits LUT-based multiplier 

    LUT_BR. vhdl

    library ieee;
    use ieee.std_logic_1164.all;
    use ieee.std_logic_arith.all;
    use ieee.std_logic_unsigned.all;

    entity LUT_BR is
    port (
    clk : in std_logic;
    a, b: in std_logic_vector(3 downto 0);
    c: out std_logic_vector(3 downto 0);
    porti : out std_logic_vector(3 downto 0);
    portj : out std_logic_vector(3 downto 0);
    portk : out std_logic_vector(3 downto 0)
    );
    end entity LUT_BR;

    architecture behavioral of LUT_BR is
    component adder_mod_m_CG
    port (
    x, y: in std_logic_vector(3 downto 0);
    addb_sub: in std_logic;
    z: buffer std_logic_vector(3 downto 0)
    );
    end component;

    signal z : std_logic := ‘0’;
    signal i : std_logic_vector(3 downto 0);
    signal j : std_logic_vector(3 downto 0);
    signal k : std_logic_vector(3 downto 0);

    begin

    process (clk)
    begin
    if clk’event and clk = ‘1’ then
    case a is
    when "0001" => i <= "0000";
    when "0010" => i <= "0001";
    when "0011" => i <= "0011";
    when "0100" => i <= "0010";
    when "0101" => i <= "0110";
    when "0110" => i <= "0100";
    when "0111" => i <= "0101";
    when others => i <= "0000";
    end case;
    case b is
    when "0001" => j <= "0000";
    when "0010" => j <= "0001";
    when "0011" => j <= "0011";
    when "0100" => j <= "0010";
    when "0101" => j <= "0110";
    when "0110" => j <= "0100";
    when "0111" => j <= "0101";
    when others => j <= "0000";
    end case;
    case k is
    when "0000" => c <= "0001";
    when "0001" => c <= "0010";
    when "0010" => c <= "0100";
    when "0011" => c <= "0011";
    when "0100" => c <= "0110";
    when "0101" => c <= "0111";
    when "0110" => c <= "0101";
    when others => c <= "0000";
    end case;
    end if;

    end process;

    adderku: adder_mod_m_CG port map (i, j, z, k);
    porti <= i;
    portj <= j;
    portk <= k;

    end architecture behavioral;

    adder_mod_m_CG.vhdl

    library ieee;
    use ieee.std_logic_1164.all;
    use IEEE.std_logic_arith.all;
    use IEEE.std_logic_unsigned.all;

    entity adder_mod_m_CG is
    port (
    x, y: in std_logic_vector(3 downto 0);
    addb_sub: in std_logic;
    z: out std_logic_vector(3 downto 0)
    );
    end adder_mod_m_CG;

    architecture rtl of adder_mod_m_CG is
    constant M: std_logic_vector(3 downto 0) := conv_std_logic_vector(7, 4);
    signal long_x, xor_y, sum1, long_z1, xor_m, sum2: std_logic_vector(4 downto 0);
    signal c1, c2, sel: std_logic;
    signal z1, z2: std_logic_vector(3 downto 0);

    begin

    long_x <= ‘0’ & x;
    xor_gates1: for i in 0 to 3 generate
    xor_y(i) <= y(i) xor addb_sub;
    end generate;
    xor_y(4) <= ‘0’;
    sum1 <= addb_sub + long_x + xor_y;
    c1 <= sum1(4);
    z1 <= sum1(3 downto 0);
    long_z1 <= ‘0’ & z1;
    xor_gates2: for i in 0 to 3 generate
    xor_m(i) <= m(i) xor not(addb_sub);
    end generate;
    xor_m(4) <= ‘0’;
    sum2 <= not(addb_sub) + long_z1 + xor_m;
    c2 <= sum2(4);
    z2 <= sum2(3 downto 0);
    sel <= (not(addb_sub) and (c1 or c2)) or (addb_sub and not(c1));
    with sel select z <= z1 when ‘0’, z2 when others;

    end rtl;

    Pair programming always works 🙂 Thank you Guru 🙂

     
  • CG 4:47 pm on November 17, 2010 Permalink | Reply
    Tags: , , LUT, , ,   

    LUT and Tristate buffer 


    library ieee;
    use ieee.std_logic_1164.all;

    entity lutmulCGver2 is
    port (
    clk : in std_logic;
    e : in std_logic;
    r : in std_logic;
    a, b: in std_logic_vector(3 downto 0);
    c: out std_logic_vector(3 downto 0);
    i, j, k : out std_logic_vector(3 downto 0);
    enA, enB, enC : in std_logic
    );
    end entity lutmulCGver2;

    architecture behavioral of lutmulCGver2 is
    -- signal i : integer range 0 to 6:=0;
    -- signal j : integer range 0 to 6:=0;
    signal tribus : std_logic_vector ( 3 downto 0 );
    signal enable : std_logic:='0';
    type alog is array (0 to 2**3 - 2) of std_logic_vector(3 downto 0);
    constant my_alog : alog := (
    0 => "0001",
    1 => "0010",
    2 => "0100",
    3 => "0011",
    4 => "0110",
    5 => "1111",
    6 => "0101");

    type log is array (1 to 2**3 - 1) of std_logic_vector(3 downto 0);
    -- type log is array (1 to 2**3 - 1) of integer;
    constant my_log : log := (
    1 => "0000",
    2 => "0001",
    3 => "0011",
    4 => "0010",
    5 => "0110",
    6 => "0100",
    7 => "0101");

    begin

    process(enA, enB, a, b)
    begin
    if enA = '1' then
    tribus <= a;
    elsif enB = '1' then
    tribus <= b;
    else
    tribus <= "ZZZZ";
    end if;
    end process;

    process(enC)
    begin
    if enC = '1' then
    c <= "0000";
    end case;
    end if;
    -- k <= (i xor j) xor "1011"; -- xor untuk mereduksi, tapi hanya
    berlaku untuk kalau generatornya x atau x+1
    end process;
    end architecture behavioral;

     
    • Budi Rahardjo 4:59 pm on November 17, 2010 Permalink | Reply

      good stuff (sambil belum dibaca tea :))

      • CG 5:08 pm on November 17, 2010 Permalink | Reply

        halah, padahal mau nanya, udah bener belum waveformsnya?

c
Compose new post
j
Next post/Next comment
k
Previous post/Previous comment
r
Reply
e
Edit
o
Show/Hide comments
t
Go to top
l
Go to login
h
Show/Hide help
shift + esc
Cancel