Generate read-address and write address for zig-zag scan of NxN matrix
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.
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.