Subversion Repositories dvb_s2_ldpc_decoder

`timescale 1ns/10ps
 
module tb_cn();
 
localparam NUM_RUNS           = 1000;
localparam ITERATIONS_PER_RUN = 30;
localparam MAX_CONNECTIVITY   = 30;
 
localparam FOLDFACTOR = 1;
localparam CN_DEPTH   = 2**(7+FOLDFACTOR);
 
localparam LLRWIDTH          = 4;
localparam MAX_LLR           = 2**(LLRWIDTH-1) -1;
localparam MAX_INTERNAL_LLR  = 2**(LLRWIDTH-2) -1;
 
localparam MIN_SEPARATION = 5;
 
localparam CLK_PERIOD = 10ns;
localparam HOLD       = 1ns;
 
localparam LASTSHIFTDIST = (FOLDFACTOR==1) ? 11 :
                           (FOLDFACTOR==2) ? 5  :
                           (FOLDFACTOR==3) ? 3  :
                           /* 4 */           2;
localparam LASTSHIFTWIDTH  = (FOLDFACTOR==1) ? 4 :
                             (FOLDFACTOR==2) ? 3 :
                             (FOLDFACTOR==3) ? 2 :
                             /* 4 */           2;
 
//////////////////////////////////////////
 
reg clk;
reg rst;
 
initial
begin
  clk <= 1;
  rst <= 1;
  #0;
 
  #(CLK_PERIOD/2) clk <= ~clk;
  #(CLK_PERIOD/2) clk <= ~clk;
  #(CLK_PERIOD/2) clk <= ~clk;
 
  rst <= #HOLD 0;
 
  forever
    #(CLK_PERIOD/2) clk <= ~clk;
end
 
/////////////////////
// Main controller //
/////////////////////
typedef struct { int iterations;
                 int connections_per_node;
                 int min_separation;
                 bit allow_adjacent_writes;
                 } run;
run run_source;
 
mailbox #( run ) run_descriptor;
semaphore        generator_done;
 
initial
begin
  run_descriptor = new();
  @(negedge rst);
 
  for( int run_num=0; run_num<NUM_RUNS; run_num++ )
  begin
    run_source.iterations            = ITERATIONS_PER_RUN;
    run_source.connections_per_node  = 2 + ({ $random() } % (MAX_CONNECTIVITY -2));
    run_source.min_separation        = MIN_SEPARATION;
    run_source.allow_adjacent_writes = 1;
 
    run_descriptor.put( run_source );
 
    generator_done.get(1);
    $display( "%0t: Run %0d done", $time(), run_num );
  end
 
  $display( "Done" );
  $stop();
end
 
////////////////////
// Data generator //
////////////////////
localparam EMPTY    = -999999;
 
int data_sequence[];
bit sign_sequence[];
bit disable_sequence[];
int address[];
 
int writes_per_iteration;
int iterations;
 
semaphore send_load;
semaphore send_run;
semaphore load_done;
semaphore run_done;
 
initial
begin
  generator_done = new();
  send_load      = new();
  send_run       = new();
 
  @(negedge rst);
 
  forever
  begin
    run run_dest;
 
    int array_len;
    bit start_over;
 
    run_descriptor.get( run_dest );
 
    writes_per_iteration = run_dest.connections_per_node*CN_DEPTH;
    iterations           = run_dest.iterations;
    array_len            = iterations*writes_per_iteration;
 
    data_sequence    = new[array_len];
    sign_sequence    = new[array_len];
    disable_sequence = new[writes_per_iteration];
    address          = new[writes_per_iteration];
 
    /////////////////////////////////////////////
    // Create data sequence for the entire run //
    /////////////////////////////////////////////
    start_over = 1;
 
    // assign random data and clear address array
    for( int i=0; i<=writes_per_iteration; i++ )
    begin
      address[i]          = EMPTY;
      disable_sequence[i] = 0;//($random() %100 == 1);
    end
 
    for( int i=0; i<=array_len; i++ )
    begin
      data_sequence[i] = { $random() } % (MAX_LLR+1);
      sign_sequence[i] = $random();
    end
 
    while( start_over )
    begin
      bit adjacent_write;
      int try_addr;
 
      start_over     = 0;
      adjacent_write = 0;
      try_addr       = 0;
 
      for( int j=0; j<CN_DEPTH; j++ )
      begin
        for( int k=0; k<run_dest.connections_per_node; k++ )
        begin
          bit good_addr;
          bit good_run;
 
          int try_count;
          // Assign somewhat random order, but try to group addresses and
          // create "runs" of identical addresses
          try_count = 0;
          good_addr = 0;
 
          while( !good_addr && !start_over )
          begin
            try_count++;
            try_addr++;
            try_addr = try_addr % writes_per_iteration;
 
            // try to group even non-adjacent writes fairly closely, to maximize the
            // likelihood of memory inconsistency
            if( !adjacent_write )
            begin
              try_addr += run_dest.min_separation - 1;
              try_addr += { $random() } % 3;
              try_addr = try_addr % writes_per_iteration;
            end
 
            // search for an empty address
            while( (address[try_addr]!=EMPTY) && (try_count!=writes_per_iteration) )
            begin
              try_count++;
              try_addr++;
              try_addr = try_addr % writes_per_iteration;
            end
 
            good_addr = (address[try_addr]==EMPTY);
 
            // check whether nearby locations contain identical addresses.  A continuous
            // run of identical addresses is allowed
            good_run = run_dest.allow_adjacent_writes;
 
            for( int test_addr=try_addr-1;
                 (test_addr >= try_addr-run_dest.min_separation) && (test_addr >= 0);
                 test_addr-- )
            begin
              bit matches1;
              matches1 = j==address[test_addr];
 
              good_run  = good_run & matches1;
              good_addr = good_addr & (!matches1 | good_run);
            end
 
            good_run = run_dest.allow_adjacent_writes;
 
            for( int test_addr=1;
                 (test_addr < run_dest.min_separation) &&
                 (try_addr+test_addr < writes_per_iteration);
                 test_addr++ )
            begin
              bit matches2;
              matches2 = j==address[try_addr+test_addr];
 
              good_run  = good_run & matches2;
              good_addr = good_addr & (!matches2 | good_run);
            end
 
            if( good_addr )
              adjacent_write = ({$random()}%3==2) & run_dest.allow_adjacent_writes;
            else // if random jump resulted in bad address, try next address
              adjacent_write = 1;
 
            // There's a chance we'll have to start all over due to impossible
            // placement.  Detect that here:
            if( !good_addr && (try_count==writes_per_iteration) )
            begin
              int ad;
              int co;
              ad = j;
              co = k;
              $display( "Address %0d / %0d, connection %0d / %0d - couldn't find good placement",
                        ad, CN_DEPTH, co, run_dest.connections_per_node );
              start_over = 1;
            end
 
            if( good_addr )
              address[try_addr] = j;
          end
        end
      end
    end
 
    // At this point, address and data_sequence contain valid data
    send_load.put(1);
    load_done.get(1);
    send_run.put(1);
    run_done.get(1);
 
    data_sequence.delete;
    sign_sequence.delete;
    disable_sequence.delete;
    address.delete;
 
    generator_done.put(1);
  end
end
 
////////////////////////////
// Load/unload transactor //
////////////////////////////
reg                   llr_access;
reg[7+FOLDFACTOR-1:0] llr_addr;
reg                   llr_din_we;
 
initial
begin
  load_done = new();
 
  llr_access  <= 0;
  llr_addr    <= 0;
  llr_din_we  <= 0;
 
  @(negedge rst);
 
  forever
  begin
    send_load.get( 1 );
    @(posedge clk);
    llr_access <= #HOLD 1;
    repeat(2) @(posedge clk);
 
    for( int i=0; i<CN_DEPTH; i++ )
    begin
      llr_addr   <= #HOLD i;
      llr_din_we <= #HOLD 1;
      @(posedge clk);
    end
 
    llr_access  <= #HOLD 0;
    llr_addr    <= #HOLD 0;
    llr_din_we  <= #HOLD 0;
    repeat(MIN_SEPARATION) @(posedge clk);
 
    load_done.put( 1 );
  end
end
 
////////////////////////////////
// Message passing transactor //
////////////////////////////////
reg                   iteration;
reg                   first_half;
reg                   first_iteration;
reg                   cn_rd;
reg                   cn_we;
reg                   disable_paritymsg;
reg[7+FOLDFACTOR-1:0] addr_cn;
 
reg[LLRWIDTH-1:0]  sh_msg;
wire[LLRWIDTH-1:0] cn_msg;
 
initial
begin
  run_done = new();
 
  iteration         <= 0;
  first_half        <= 0;
  first_iteration   <= 0;
  cn_rd             <= 0;
  cn_we             <= 0;
  disable_paritymsg <= 0;
  addr_cn           <= 0;
  sh_msg            <= 0;
 
  @(negedge rst);
 
  forever
  begin
    send_run.get( 1 );
    @(posedge clk);
 
    // downstream
    for( int it=0; it<iterations; it++ )
    begin
      int base_offset;
      base_offset = it * writes_per_iteration;
 
      iteration <= #HOLD it[0];
 
      for( int half=0; half<2; half++ )
      begin
        first_half      <= #HOLD half==0;
        first_iteration <= #HOLD it==0;
        cn_rd           <= #HOLD half==1;
        cn_we           <= #HOLD half==0;
 
        for( int i=0; i<writes_per_iteration; i++ )
        begin
          sh_msg[LLRWIDTH-1]   <= #HOLD sign_sequence[base_offset + i];
          sh_msg[LLRWIDTH-2:0] <= #HOLD data_sequence[base_offset + i];
          addr_cn              <= #HOLD address[i];
          disable_paritymsg    <= #HOLD disable_sequence[i];
          @(posedge clk);
        end
 
        cn_rd <= #HOLD 0;
        cn_we <= #HOLD 0;
        repeat(2* MIN_SEPARATION) @(posedge clk);
      end
    end
 
    repeat(2) @(posedge clk);
    run_done.put( 1 );
  end
end
 
///////////////////////
// Model and checker //
///////////////////////
// Store states based on received and sent messages
localparam CN_MSG_LATENCY = 4;
 
int recv_counter[0:CN_DEPTH-1];
int send_counter[0:CN_DEPTH-1];
int last_recv_iteration[0:CN_DEPTH-1];
int last_send_iteration[0:CN_DEPTH-1];
int recv_msgs[0:CN_DEPTH-1][0:MAX_CONNECTIVITY-1];
int sent_msgs[0:CN_DEPTH-1][0:MAX_CONNECTIVITY-1];
 
bit cn_rd_del[0:CN_MSG_LATENCY-1];
int addr_cn_del[0:CN_MSG_LATENCY-1];
 
always @( posedge clk )
begin
  if( llr_access && llr_din_we )
  begin
    last_recv_iteration[llr_addr] = -1;
    last_send_iteration[llr_addr] = -1;
    for( int i=0; i<MAX_CONNECTIVITY; i++ )
    begin
      recv_msgs[llr_addr][i] = EMPTY;
      sent_msgs[llr_addr][i] = 0;
    end
  end
 
  // Writes
  if( cn_we & !disable_paritymsg )
  begin
    int new_sign;
    int new_mag;
    int new_msg;
    int sent_msg;
 
    // increment counter, or reset counter for new iteration
    if( last_recv_iteration[addr_cn]!=iteration )
      recv_counter[addr_cn] = 0;
    else
      recv_counter[addr_cn]++;
 
    last_recv_iteration[addr_cn] = iteration;
 
    // stored value = received message - sent message, since a node's own
    // contribution to the LLR needs to be ignored
    new_sign  = sh_msg[LLRWIDTH-1] ? -1 : 1;
    new_mag   = sh_msg[LLRWIDTH-2:0];
    sent_msg  = sent_msgs[addr_cn][ recv_counter[addr_cn] ];
 
    new_msg = new_sign * new_mag;
    new_msg = new_msg - sent_msg;
 
    new_sign = new_msg < 0 ? -1 : 1;
    new_mag  = new_sign * new_msg;
 
    if( new_mag>MAX_INTERNAL_LLR )
      new_mag = MAX_INTERNAL_LLR;
 
    recv_msgs[addr_cn][ recv_counter[addr_cn] ] = new_sign * new_mag;
  end
 
  // Reads
  cn_rd_del[0]   <= cn_rd;
  addr_cn_del[0] <= addr_cn;
  for( int i=1; i<CN_MSG_LATENCY; i++ )
  begin
    cn_rd_del[i]   <= cn_rd_del[i-1];
    addr_cn_del[i] <= addr_cn_del[i-1];
  end
 
  if( cn_rd_del[CN_MSG_LATENCY-1] )
  begin
    int new_sign;
    int new_mag;
    int delayed_addr;
    int min_prev_val;
 
    delayed_addr = addr_cn_del[CN_MSG_LATENCY-1];
 
    // increment counter, or reset counter for new iteration
    if( last_send_iteration[delayed_addr]!=iteration )
      send_counter[delayed_addr] = 0;
    else
      send_counter[delayed_addr]++;
 
    last_send_iteration[delayed_addr] = iteration;
 
    // store read value in matrix
    new_sign = cn_msg[LLRWIDTH-1] ? -1 : 1;
    new_mag  = cn_msg[LLRWIDTH-2:0];
 
    sent_msgs[delayed_addr][ send_counter[delayed_addr] ] = new_sign * new_mag;
  end
end
 
// predict messages
int predicted_msgs[0:CN_DEPTH-1][0:MAX_CONNECTIVITY-1];
 
always @( posedge cn_rd )
begin
  for( int node=0; node<CN_DEPTH; node++ )
  begin
    // find min, nextmin for each node
    int min, nextmin;
    int sign_product;
 
    min     = 999999;
    nextmin = 999999;
 
    for( int msg_num=0; msg_num<=recv_counter[node]; msg_num++ )
    begin
      int msg_sign;
      int msg_mag;
      msg_sign = recv_msgs[node][msg_num] < 0 ? -1 : 1;
      msg_mag  = msg_sign * recv_msgs[node][msg_num];
 
      if( msg_mag <= min )
      begin
        nextmin = min;
        min     = msg_mag;
      end
      if( (msg_mag<nextmin) && (msg_mag!=min) )
        nextmin = msg_mag;
    end
 
    if( nextmin==999999 )
      nextmin = min;
 
    // find XOR of received signs
    sign_product = 1;
    for( int i=0; i<=recv_counter[node]; i++ )
      sign_product *= recv_msgs[node][ i ] < 0 ? -1 : 1;
 
    // assign EMPTY, or positive or negative min or nextmin to each message
    for( int msg_num=0; msg_num<MAX_CONNECTIVITY; msg_num++ )
    begin
      if( msg_num>recv_counter[node] )
        predicted_msgs[node][msg_num] = EMPTY;
      else
      begin
        int msg_sign;
        int msg_mag;
        msg_sign = recv_msgs[node][msg_num] < 0 ? -1 : 1;
        msg_mag  = msg_sign * recv_msgs[node][msg_num];
 
        if( msg_mag==min )
          predicted_msgs[node][msg_num] = nextmin;
        else
          predicted_msgs[node][msg_num] = min;
 
        if( predicted_msgs[node][msg_num]>MAX_LLR )
          predicted_msgs[node][msg_num] = MAX_LLR;
        if( predicted_msgs[node][msg_num]<-1 * MAX_LLR )
          predicted_msgs[node][msg_num] = -1 * MAX_LLR;
 
        predicted_msgs[node][msg_num] *= msg_sign * sign_product;
      end
    end
  end
end
 
// Check that sent messages match predicted
int predicted;
int predicted_counter[0:CN_DEPTH-1];
 
always @( posedge clk )
begin
  // clear counters on rising edge of cn_rd
  if( cn_rd_del[CN_MSG_LATENCY-2] && !cn_rd_del[CN_MSG_LATENCY-1] )
    for( int i=0; i<CN_DEPTH; i++ )
      predicted_counter[i] = 0;
 
  if( cn_rd_del[CN_MSG_LATENCY-1] )
  begin
    int node;
    int msg_num;
    int cn_msg_int;
 
    node    = addr_cn_del[CN_MSG_LATENCY-1];
    msg_num = predicted_counter[node];
 
    cn_msg_int = cn_msg[LLRWIDTH-2:0];
    if( cn_msg[LLRWIDTH-1] )
      cn_msg_int *= -1;
 
    predicted = predicted_msgs[node][msg_num];
 
    if( predicted!=cn_msg_int )
      $display( "%0t: Mismatch, predicted cn_msg != actual, %0d != %0d",
                $time(), predicted, cn_msg_int );
 
    predicted_counter[node]++;
  end
end
 
///////////////
// DUT + RAM //
///////////////
wire                         dnmsg_we;
wire[7+FOLDFACTOR-1:0]       dnmsg_wraddr;
wire[7+FOLDFACTOR-1:0]       dnmsg_rdaddr;
wire[17+4*(LLRWIDTH-1)+31:0] dnmsg_din;
wire[17+4*(LLRWIDTH-1)+31:0] dnmsg_dout;
 
ldpc_cn #( .FOLDFACTOR    ( FOLDFACTOR ),
           .LLRWIDTH      ( LLRWIDTH )
) ldpc_cn_i(
  .clk              (clk),
  .rst              (rst),
  .llr_access       (llr_access),
  .llr_addr         (llr_addr),
  .llr_din_we       (llr_din_we),
  .iteration        (iteration),
  .first_half       (first_half),
  .first_iteration  (first_iteration),
  .cn_we            (cn_we),
  .cn_rd            (cn_rd),
  .disable_paritymsg(disable_paritymsg),
  .addr_cn          (addr_cn),
  .sh_msg           (sh_msg),
  .cn_msg           (cn_msg),
  .dnmsg_we         (dnmsg_we),
  .dnmsg_wraddr     (dnmsg_wraddr),
  .dnmsg_rdaddr     (dnmsg_rdaddr),
  .dnmsg_din        (dnmsg_din),
  .dnmsg_dout       (dnmsg_dout)
);
 
ldpc_ram_behav #(
  .WIDTH    ( 17+4*(LLRWIDTH-1)+32 ),
  .LOG2DEPTH( 7+FOLDFACTOR )
) ldpc_cnholder_i (
  .clk   ( clk ),
  .we    ( dnmsg_we ),
  .din   ( dnmsg_din ),
  .wraddr( dnmsg_wraddr ),
  .rdaddr( dnmsg_rdaddr ),
  .dout  ( dnmsg_dout )
);
 
endmodule