Сгенерируйте адрес чтения и адрес записи для зигзагообразного сканирования матрицы NxN
В моей аппаратной конструкции доступ к данным должен осуществляться зигзагообразным образом. У меня есть решение, которое дает мне последовательность адресов чтения для матрицы 8x8, так что мы читаем ее зигзагообразным образом. Однако я не могу найти что-то, что дает последовательность адресов записи.
Вот изображение для справки:
Исходные данные поступают в последовательности 0,1,2,3,4,5,6,7,.. 62,63. ZZ Scan Read предоставляет последовательность адресов чтения, которую можно использовать для чтения данных, так что мы считываем данные в зигзагообразном порядке. У меня есть программа, которая может генерировать последовательность адресов чтения ZZ Scan для матрицы NxN. Вот:
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;
Я передал последовательность чтения ZZ Scan в
Для данной входной последовательности ZZ Scan Write дает адрес записи, так что, когда мы читаем данные в той же естественной последовательности, используя адрес 0,1,2,3,4,5 ... 63, мы получим вывод, который является фактический порядок зигзагообразного сканирования. Это альтернатива использованию ZZ Scan Read.
Мой вопрос: существует ли стандартное решение для этого? Я не могу его найти.
«Я передал последовательность чтения ZZ Scan в ChatGPT, и он дал мне решение» — серьезно?! Как вы думаете, как долго вы сможете работать, если попросите ChatGPT написать для вас код?
У меня нет на это времени, да и вообще это не входит в мою повседневную работу.
Ответы 3
Рассмотрим задние диагонали в левом верхнем треугольнике. Каждая диагональ начинается с «треугольного числа» (0,1,3,6,10,15,21...) и ее направление зависит от четности числа диагоналей.
Правый нижний треугольник симметричен левому верхнему относительно центра матрицы, но значения тоже должны быть зеркальными (60=63-3).
Скрипт Python (//2 — целочисленное деление):
def genzzwr(n):
res = []
nsqm1 = n * n - 1
for y in range(n):
for x in range(n):
diag = y + x
if diag < n:
start = diag * (diag + 1) // 2
if diag % 2:
res.append(start + y)
else:
res.append(start + x)
#bad-readable reduction for 4 lines above:
#res.append(start + y*(diag%2) + x*(1-diag%2))
else:
mx = n - 1 - x
my = n - 1 - y
diag = mx + my
if diag % 2:
res.append(nsqm1 - start - my)
else:
res.append(nsqm1 - start - mx)
return res
print(genzzwr(8))
[0, 1, 5, 6, 14, 15, 27, 28, 2, 4, 7, 13, 16, 26, 29, 42,
3, 8, 12, 17, 25, 30, 41, 43, 9, 11, 18, 24, 31, 40, 44, 53,
10, 19, 23, 32, 39, 45, 52, 54, 20, 22, 33, 38, 46, 51, 55, 60,
21, 34, 37, 47, 50, 56, 59, 61, 35, 36, 48, 49, 57, 58, 62, 63]
У матрицы зигзагообразного сканирования должно быть определенное имя, вы знаете, что это такое? Я использовал chatgpt, но программа (как и ожидалось) выглядела запутанной, она сказала, что оба они представляют собой тип зигзагообразного сканирования, но не смогла предоставить мне программу.
@gyuunyuu Я не знаю. Возможно диагональное сканирование или что-то в этом роде. Обратите внимание, что эта задача обратна обычной задаче обучения (печать матрицы в зигзагообразном порядке), поэтому она может встречаться довольно редко.
Представьте себе путешественника, начинающего свой путь с северного (row=0) западного (col=0) угла. Если row+col четно, то путешественник идет на северо-восток, иначе — на юго-запад. Если путешественник заблокирован северной или восточной границей, он, если возможно, идет на восток, в противном случае — на юг. Если путешественник заблокирован западной или южной границей, он, если возможно, идет на юг, в противном случае — на восток. В VHDL 2008:
function add_gen(dim: positive) return integer_vector is
variable addr_list: integer_vector(0 to dim**2 - 1);
variable row: integer range 0 to dim - 1 := 0;
variable col: integer range 0 to dim - 1 := 0;
begin
addr_list(0) := 0;
for i in 1 to dim**2 - 1 loop
assert row /= dim - 1 or col /= dim - 1 severity failure;
if (row + col) mod 2 = 0 then
if row /= 0 and col /= dim - 1 then
row := row - 1;
col := col + 1;
elsif col = dim - 1 then
row := row + 1;
else
col := col + 1;
end if;
else
if row /= dim - 1 and col /= 0 then
row := row + 1;
col := col - 1;
elsif row /= dim - 1 then
row := row + 1;
else
col := col + 1;
end if;
end if;
addr_list(i) := row * dim + col;
end loop;
return addr_list;
end function add_gen;
Примечание: если вам необходимо синтезировать это, я рекомендую использовать функцию add_gen для инициализации константы:
architecture bar of foo is
constant my_addr: integer_vector(0 to 63) := add_gen(8);
begin
...
add <= to_stdulogicvector(my_addr(56), 6);
...
end architecture bar;
Я написал этот генератор адресов зигзагообразного сканирования, описав его как аппаратную модель, использующую двухбитное состояние для конечного автомата Мили, 3-битные счетчики обратного/обратного хода X и Y и четыре трехбитных компаратора равенства (N X N, где N = 8) для использования. с аппаратным декодером JPEG. Имеется пять выходных параметров, включая элементы управления «готово» и «увеличение/уменьшение» счетчиков, а также позволяет разрешить горизонтальное или вертикальное векторное рисование (длиной 1).
Он демонстрирует, что можно придумать с помощью цифрового дизайна. (Все это было сделано вручную.)
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;
Конечный автомат (Мили) определяет четыре вектора, которые рисуются при зигзагообразном сканировании, определяя следующий вектор за текущим вектором и встречая границы массива N x N с использованием X и Y.
Тип записи и постоянный массив записей являются лишь краткими, чтобы не загромождать конечный автомат выходными данными в каждом состоянии. Он должен быть пригодным для синтеза. Если возникнет проблема, записи можно будет заменить векторами фиксированной длины с немного большим количеством клея.
Эта диаграмма:
использовался, чтобы определить, какой вектор указать при наезде на границу или на границе.
Самый простой способ реализовать это — использовать ПЗУ. Я не думаю, что явный код имеет какие-либо преимущества. Я мог бы подумать, что это упражнение по программированию, но нет, вы использовали ChatGpt, поэтому вам просто нужен окончательный код. Зачем? Загадка.