冒泡排序

Question

誰能幫我寫VHDL代碼冒泡排序給出的數據作爲輸入數組？

我已宣佈in_array爲包含15的數組元素的輸入。我想按降序對它們進行排序。

in_array是輸入數組。 sorted_array是輸出數組。 in_array_sig是in_array

我與陳述所面臨的內部過程

以下問題類型的信號是我的代碼：

architecture behav of Bubblesort is 
    signal in_array_sig : bubble; 
    signal temp : std_logic_vector(3 downto 0); 
    signal i : integer := 0; 
begin 

    in_array_sig <= in_array; 

    proc1 : process(clk, reset) 
    begin 
    if reset = '0' then 
     if (clk'event and clk = '1') then 
     while (i <= 15) loop 
      if (in_array_sig(i) < in_array_sig(i + 1)) then 
      temp <= in_array_sig(i); 
      in_array_sig(i) <= in_array_sig(i + 1); 
      in_array_sig(i + 1) <= temp; 
      end if; 
      i <= i + 1; 
     end loop; 
     end if; 
    end if; 
    end process; 

    sorted_array <= in_array_sig; 

end behav; 

我初學VHDL編碼。請幫助我。

Answer 1

缺乏一個Minimal Complete and Verifiable example使得很難提供有關的所有事情停止從冒泡排序準確代碼的答案。這些可以按照您遇到的故障排除順序進行描述。

proc1 : process(clk, reset) 
    begin 
    if reset = '0' then 
     if (clk'event and clk = '1') then 
     while (i <= 15) loop 
      if (in_array_sig(i) < in_array_sig(i + 1)) then 
      temp <= in_array_sig(i); 
      in_array_sig(i) <= in_array_sig(i + 1); 
      in_array_sig(i + 1) <= temp; 
      end if; 
      i <= i + 1; 
     end loop; 
     end if; 
    end if; 
    end process; 

開始之前請注意，時鐘門控復位。您可以通過重置限定分配，使其成爲啓用。

問題

，我們會發現產生MCVE和測試平臺的第一件事是，過程永遠不會中止。這是由while循環中的條件引起的，這取決於我和我在處理過程中更新的信號。我不應該是這裏的信號（也可以在這裏使用for循環）。

這還指出，溫度是一個信號，並遭受同樣的問題，你不能使用臨時的「新」值，直到進程已經掛起和恢復。信號計劃更新，沒有波形元素的信號分配包含after子句，其隱含的after子句具有零延遲。當計劃恢復的進程尚未恢復並隨後暫停時，信號更新不會發生。這允許在順序語句中發現分配的信號的併發性的外觀（併發語句具有包含等效的順序語句的等同過程）。因此，在執行一系列語句的過程中，我和temp都不能更新，並且都希望成爲變量。

我們希望也得到使用in_array_sig信號咬傷。當你增加i時，先前索引的in_array_sig（i + 1）變成下一個循環迭代的in_array_sig（i）。沒有干預過程暫停和恢復原始值是可用的。 in_array_sig也想成爲一個變量。

如果我們要解決所有這些問題，我們也可能會注意到我沒有初始化（這將在for循環迭代方案中處理），我們也可能會發現我們在一行中得到了一個綁定錯誤使用in_array_sig的（i + 1）索引。如果沒有提供MCVe的問題的作者不清楚數組大小是16（編號0到15）還是17.如果前i = 15 + 1將超出in_array的未公開數組類型的索引範圍， in_array_sig和sorted_array。

如果我們要確保索引範圍得到滿足，並注意到我們只需要比數組中元素的數量少1個測試和交換，我們就會發現這個過程並不是一個完整的冒泡排序。我們會看到in_array_sig的最大二進制值作爲sorted_array的最右側元素。但是其餘元素的順序不能保證。

要執行完整的氣泡排序，我們需要嵌套第一個循環的另一個循環。此外，現在的'inner'for循環可以有越來越少的要遍歷的元素，因爲每次迭代都會保留最大的剩餘元素，直到確保訂單完成。

修復

固定上面會給我們的東西，看起來像這樣：

architecture foo of bubblesort is 
    use ieee.numeric_std.all; 
begin 

BSORT: 
    process (clk) 
     variable temp:  std_logic_vector (3 downto 0); 
     variable var_array:  bubble;   
    begin 
     var_array := in_array; 
     if rising_edge(clk) then 
      for j in bubble'LEFT to bubble'RIGHT - 1 loop 
       for i in bubble'LEFT to bubble'RIGHT - 1 - j loop 
        if unsigned(var_array(i)) > unsigned(var_array(i + 1)) then 
         temp := var_array(i); 
         var_array(i) := var_array(i + 1); 
         var_array(i + 1) := temp; 
        end if; 
       end loop; 
      end loop; 
      sorted_array <= var_array; 
     end if; 
    end process; 
end architecture foo; 

注意循環迭代計劃型泡沫界限來描述，外比一個短每個迭代的長度和內部縮短一個。另請注意，sorted_array分配已移至in_array_sig變量替換var_array可見的進程中。

另外值得注意的是使用無符號大於運算符。 std_logic_vector的「>」允許元值和'H'和'L'值扭曲關係比較，而無符號運算符則是算術運算。

結果在包裝和實體聲明

投擲：

library ieee; 
use ieee.std_logic_1164.all; 

package array_type is 
    type bubble is array (0 to 15) of std_logic_vector(3 downto 0); 
end package; 

library ieee; 
use ieee.std_logic_1164.all; 
use work.array_type.all; 

entity bubblesort is 
    port (
     signal clk:    in std_logic; 
     signal reset:   in std_logic; 
     signal in_array:  in bubble; 
     signal sorted_array: out bubble 
    ); 
end entity; 

與測試平臺一起：

library ieee; 
use ieee.std_logic_1164.all; 
use work.array_type.all; 

entity bubblesort_tb is 
end entity; 

architecture fum of bubblesort_tb is 
    signal clk:    std_logic := '0'; 
    signal reset:   std_logic := '0'; 
    signal in_array:  bubble := 
        (x"F", x"E", x"D", x"C", x"B", x"A", x"9", x"8", 
        x"7", x"6", x"5", x"4", x"3", x"2", x"1", x"0"); 
    signal sorted_array: bubble; 
begin 

DUT: 
    entity work.bubblesort(foo) 
     port map (
      clk => clk, 
      reset => reset, 
      in_array => in_array, 
      sorted_array => sorted_array 
     ); 
CLOCK: 
    process 
    begin 
     wait for 10 ns; 
     clk <= not clk; 
     if now > 30 ns then 
      wait; 
     end if; 
    end process; 

end architecture; 

，我們得到：

有用的東西。

重置爲啓用未包含在架構中的進程BSORT中，並且可以在具有時鐘邊沿條件的if語句內添加。

關於這裏我們得到了馬修泰勒關於描述硬件的評論。

根據綜合工具的不同，過程可能或可能不能作爲硬件實現。如果不是，你需要中間變量來保存內循環的每個連續迭代中使用的數組部分。

還有一個問題，你可以在一個時鐘週期中做多少。最壞的情況是由15個元素比較和15個2：2選擇器有條件地交換元素對組成的延遲深度。

如果您選擇與合成延遲不兼容的時鐘速度，您需要將實現從軟件循環仿真重新架構到在連續時鐘上運行的某個操作。

這可以像允許更多的時鐘週期一樣簡單，通過使用該啓用來確定何時冒泡排序對於加載到sorted_array寄存器是有效的。它可能更復雜，也允許不同的和更好的執行排序方法或修改冒泡排序來表示檢測不需要更多的掉期。