Generate read-address and write address for zig-zag scan of NxN matrix

Question

In my hardware design, data needs to be accessed in zig-zag fashion. I have a solution that gives me read-address sequence for an 8x8 matrix such that we are reading it in zig-zag way. However, I am unable to find something that gives write address sequence.

Here is the image for guidance:

The original data comes in sequence 0,1,2,3,4,5,6,7,.. 62,63. The ZZ Scan Read gives read address sequence to use to read the data such that we get the data read out in zig-zag order. I have program that can generate the ZZ Scan Read address sequence for NxN matrix. Here it is:

  generic (ADDR_WIDTH : INTEGER);
  subtype addr_value_t is integer range 0 to 2**ADDR_WIDTH-1;
  type addr_list_t is array(0 to 2**ADDR_WIDTH-1) of addr_value_t;

  function int_sqrt(n: natural)
    return natural is
    variable r : natural := 0;
  begin
    while (r * r < n) loop
        r := r + 1;
    end loop;
    return r;
  end function;

  function generate_addr_array_4
    return addr_list_t is
    variable addr_list : addr_list_t;
    variable dim       : integer := int_sqrt(2**ADDR_WIDTH);
    variable dimdim    : integer := dim*dim;
    variable row       : integer := 0;
    variable col       : integer := 0;
    variable direction : integer := 0;
  begin
    if dimdim = 2**ADDR_WIDTH then
      for i in 0 to dimdim-1 loop
        addr_list(i) := row * dim + col;
        if direction = 0 then   -- moving up
            if col = dim-1 then
                row := row + 1;
                direction := 1;
            elsif row = 0 then
                col := col + 1;
                direction := 1;
            else
                col := col + 1;
                row := row - 1;
            end if;
        else                    -- moving down
            if row = dim-1 then
                col := col + 1;
                direction := 0;
            elsif col = 0 then
                row := row + 1;
                direction := 0;
            else
                col := col - 1;
                row := row + 1;
            end if;
        end if;
      end loop;
    else
      null;
    end if;
    return addr_list;
  end function;

I gave the ZZ Scan Read sequence to ChatGPT and it gave me a solution. I had to modify it and debug it to make it work. However, ChatGPT has completely failed to give me a program for the ZZ Scan Write and I am not sure how to write it.

For a given input sequence the ZZ Scan Write gives the write address such that when we read the data in the same natural sequence using address 0,1,2,3,4,5 ... 63, we shall get output that is the actual zig-zag scan order. This is alternative to using the ZZ Scan Read.

My question is, does a standard solution for this exist? I am unable to find it.

Answer 1

I had written this zig zag scan address generator describing it as a hardware model using a two bit state for a Mealy state machine, 3 bit X and Y up/down counters and four three bit equality comparators (N X N where N = 8) for use with hardware JPEG decoder. There are five outputs including a done and increment/decrement controls for the counters as well as enables to allow horizontal or vertical vector drawing (of a length of 1).

It demonstrates what you can come up with by digital design. (This was all hand done.)

library ieee;
use ieee.std_logic_1164.all;
use ieee.numeric_std.all;

entity diagonal_scan is
    generic (
        constant N:     positive := 8;  -- Power of 2  
        constant LEN:   positive := 3   --  integer(log2(real(N))); -2008
    );
    port (
        clk:    in  std_logic;
        reset:  in  std_logic;
        enab:   in  std_logic;
        output: out std_logic_vector (2 * LEN - 1  downto 0);
        done:   out std_logic
    );
end entity;

architecture vectors of diagonal_scan is
    signal x, y:    unsigned (LEN - 1 downto 0) := (others => '0');
    subtype ctr is  unsigned (x'range);
    signal xmin:    std_logic;
    signal ymin:    std_logic;
    signal xmax:    std_logic;
    signal ymax:    std_logic;
    
    type vector_rec is record
        xdir:   std_logic;
        ydir:   std_logic;
        xenab:  std_logic;
        yenab:  std_logic;
    end record;
    
    type vect is (HR, VB, UR, LL); 
    signal state, next_state: vect;
    type vector_type is array (vect range HR to LL) of vector_rec;
    signal xdir, ydir, xenab, yenab: std_logic;
    constant vector: vector_type := (
        HR => (           -- HORIZONTAL to RIGHT
            xdir => '1',  -- where '1' is increment and '0 is decrement
            ydir => '1',  -- don't care here
            xenab => '1',
            yenab => '0'  -- becase y is not enabled
        ),
        VB => (           -- VERTICAL to BOTTOM
            xdir => '1',  -- don't care here
            ydir => '1',
            xenab => '0',
            yenab => '1'
        ),
        UR => (           -- toward UPPER RIGHT
            xdir => '1',
            ydir => '0',  
            xenab => '1',
            yenab => '1'
        ),
        LL => (           -- toward LOWER LEFT
            xdir => '0',
            ydir => '1',  
            xenab => '1',
            yenab => '1'
        )
    );

begin
    
    (xdir, ydir, xenab, yenab) <= vector(next_state);
    
    xmin <= '1' when x = ctr'(others => '0') else
            '0';

    ymin <= '1' when y = ctr'(others => '0') else
            '0';

    xmax <= '1' when x = ctr'(others => '1') else
            '0';

    ymax <= '1' when y = ctr'(others => '1') else
            '0';

CONTROL:
    process (clk)
    begin
        if reset = '1' then
            state <= HR;
        elsif rising_edge(clk) and enab = '1' then
            state <= next_state;
        end if;
    end process;

MEALY_FSM:
    process (state, xmin, ymin, xmax, ymax)
    begin
        done <= '0';
        next_state <= state;
        case state is
            when HR =>              -- length one
                if ymin = '1' and x(0) = '1' then
                    next_state <= LL;
                elsif ymax = '1' then
                    next_state <= UR;
                end if;
                if ymax = '1' and xmax = '1' then
                    done <= '1';
                end if;
            when VB =>              -- length one
                if xmin = '1' then
                    next_state <= UR;
                elsif xmax = '1' then
                    next_state <= LL;
                end if;
            when UR =>
                 if xmax = '1' then
                     next_state <= VB;
                 elsif ymin = '1' then
                     next_state <= HR;
                 end if;
            when LL =>
                if ymax = '1' then
                    next_state <= HR;
                elsif xmin = '1' then
                    next_state <= VB;
                end if;
        end case;
    end process;

XCNTR:
    process (clk)
    begin
        if rising_edge(clk) then
            if reset = '1' then
                x <= (others => '0');
            elsif enab = '1' and xenab = '1' then
                if xdir = '1' then
                    x <= x + 1;
                elsif xdir = '0' then
                    x <= x - 1;
                end if;
            end if;
        end if;
    end process;

YCNTR:
    process (clk)
    begin
        if rising_edge(clk) then
            if reset = '1' then
                y <= (others => '0');
            elsif enab = '1' and yenab = '1' then
                if ydir = '1' then
                    y <= y + 1;
                elsif ydir = '0' then
                    y <= y - 1;
                end if;
            end if;
        end if;
    end process;

    output <= std_logic_vector (y & x);

end architecture;

library ieee;
use ieee.std_logic_1164.all;

entity diagonal_scan_tb is
end entity;

architecture testbench of diagonal_scan_tb is
    use ieee.math_real.all;
    constant N:     positive := 8;  -- Power of 2
    constant LEN:   positive := integer(log2(real(N))); -- otherwise CEIL
    
    signal clk:     std_logic := '0';
    signal reset:   std_logic := '1';
    signal enab:    std_logic := '0';
    signal output:  std_logic_vector (2 * LEN - 1  downto 0);
    signal done:    std_logic;
begin
DUT:
    entity work.diagonal_scan
        generic map (
            N => N,
            LEN => LEN
        )
        port map (
            clk => clk,
            reset => reset,
            enab => enab,
            output => output,
            done => done
        );

CLOCK:
    process
    begin
        wait for 10 ns;
        clk <= not clk;
        if now > 1400 ns then
            wait;
        end if;
    end process;

STIMULI:
    process
    begin
        wait for 40 ns;
        reset <= '0';
        wait for 40 ns;
        enab <= '1';
        wait until done = '1';
        reset <= done;
        wait until rising_edge(clk);
        enab <= '0';
        reset <= '0';
        wait;
    end process;
    
end architecture;

The Finite State Machine (Mealy) specifies the four vectors that are drawn in the zig zag scan specifying the next vector by the current vector and encountering the boundaries to an N x N array using X and Y.

The record type and constant array of records is just short hand to avoid cluttering up the state machine with the outputs in every state. It should be synthesis eligible. If there were to be a problem the records could be replaced by a fixed length vectors with slightly more glue.

This diagram:

was used to determine which vector to specify when running into or on a boundary.