VHDLでの丸め

# はじめに

[Wikipedia](https://ja.wikipedia.org/wiki/%E7%AB%AF%E6%95%B0%E5%87%A6%E7%90%86#%E4%BA%94%E6%8D%A8%E4%BA%94%E8%B6%85%E5%85%A5)にもあるように丸め方にはいくつかの方法があります。
それぞれ一長一短があるため、適切な丸めを選択するべきです。
今回はそれぞれの特性について概要とVHDLでの参考の実装をまとめます。

この記事では以下のような想定をおいています。

* 入力値(`i_data`)と出力値(`o_data`)は符号付き固定小数点2進数(`signed`)
* 入力より出力のビット幅が小さい(`i_data'length > o_data'length`)
* 入力値の分布に偏りがない

今回はすべて組み合わせ回路として実装していますが、
実際には適宜パイプライン化する必要があるでしょう。

# 切り捨て・切り上げ
比較的単純な実装で実現できるメリットがあります。
ここでは切り捨てと0への丸めを紹介します。

## 切り捨て (truncate)

<img width="800" alt="table_truncate.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/313464/cbfef079-5fbb-595c-58ff-16db43e0b3d9.png">
切り捨ては余分な下位ビットを取り除くだけです。
切り捨ては最も単純に実装できますが、バイアスがのるため注意が必要です。

```vhdl:truncate.vhd
-- truncate
o_data <= i_data(i_data'length - 1 downto i_data'length - o_data'length);
```

<img width="480" alt="truncate.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/313464/3f6cec0a-d231-5afb-053e-89bfd2142f33.png">
グラフからマイナス側にバイアスがのっていることがわかります。

## 0への丸め(rounding toward zero : RZ)

<img width="800" alt="table_round_toward_zero.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/313464/3397486e-c912-bdc5-9e1c-5c63383fa699.png">
0への丸めは切り捨てに比べてバイアスがのらない点がメリットになります。
しかし、加算が入る分だけパスが長くなります。

以下の実装では入力値の正負によってaddを変更しています。

* `i_data >= 0`のときは`add = B"0.000..."`を足して切り捨て(= 切り捨て)
* `i_data < 0`のときは`add = B"0.111..."`を足して切り捨て(= 切り上げ)

```vhdl:round_toward_zero.vhd
-- round_toward_zero
signal add : signed(i_data'length - o_data'length downto 0);
signal sum : signed(i_data'length downto 0) := (others => '0');

add <= (add'length - 1 => '0', others => i_data(i_data'length - 1));
sum <= resize(i_data, sum'length) + resize(add, sum'length);

o_data <= sum(i_data'length - 1 downto i_data'length - o_data'length);
```

<img width="480" alt="round_toward_zero.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/313464/79430493-0dc9-e5ec-b224-22f05a31bb84.png">
グラフから、切り捨てと比べてバイアスが消えていることがわかります。

# 最近接丸め

<img width="800" alt="table_round_to_the_nearest.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/313464/b4bfd89b-b0af-ee44-2802-5575cba0ae97.png">
名前通り、最も近い値に丸める方法です。
最も近い値が二つある場合にどうするかでパターンが分かれます。
切り捨て・切り上げと比べて誤差が小さくなるメリットがあります。
ここでは0捨1入と偶数への丸めを紹介します。


## 0捨1入 (round half up)

<img width="800" alt="table_round_half_up.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/313464/13b1158d-97ce-9555-cf78-511fb73ee689.png">
四捨五入の2進数バージョンです。
最近接値が二つある場合は大きいほうに丸めます。

VHDLにはRound関数がないので0.5加算して切り捨てするのと同様の実装を行います。
加算を行う都合上、最大値を入れるとオーバーフローしてしまう点には注意が必要です。

飽和処理を入れるかどうかは仕様によるでしょう。

最近接値が二つある場合は常に切り上げるように丸めているためバイアスがのる点には注意が必要です。

```vhdl:round_half_up.vhd
-- round half up
constant add : signed(i_data'length - 1 downto 0) := (i_data'length - o_data'length - 1 => '1', others => '0');
signal sum : signed(i_data'length downto 0) := (others => '0');

sum <= resize(i_data, sum'length) + resize(add, sum'length);

-- WARNING : overflow
o_data <= sum(i_data'length - 1 downto i_data'length - o_data'length);
```

<img width="480" alt="round_half_up.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/313464/b1513aa3-136a-c17d-95c0-bbd5e1f213b2.png">
わかりにくいですが、常に切り上げるためプラス側にバイアスがのります。

## 偶数への丸め (round to even)

<img width="800" alt="table_round_to_even.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/313464/e42faafe-8aaf-3c70-e209-c011f0a4384e.png">
最近接値が二つある場合は偶数になるように丸めます。

0捨1入では値が常に切り上げられていましたが、
偶数丸めでは切り捨てと切り上げが半々になるためバイアスがのらなくなります。

実装としては以下のような内容になります。

* 0.5加算したあとの値が整数の場合、切り捨てしたあとにLSBを0にする。
* 整数でない場合はそのまま切り捨てする。

0捨1入と同様に、最大値を入れるとオーバーフローしてしまう点には注意が必要です。

```vhdl:round_to_even.vhd
-- round to even
constant pattern : signed(i_data'length - o_data'length - 1 downto 0) := (others => '0');
constant add : signed(i_data'length - 1 downto 0) := (i_data'length - o_data'length - 1 => '1', others => '0');
signal sum : signed(i_data'length downto 0) := (others => '0');

sum <= resize(i_data, sum'length) + resize(add, sum'length);

-- WARNING : overflow
process(sum)
begin
    if sum(i_data'length - o_data'length - 1 downto 0) = pattern then
        o_data <= sum(i_data'length - 1 downto i_data'length - o_data'length + 1) & '0';
    else
        o_data <= sum(i_data'length - 1 downto i_data'length - o_data'length);
    end if;
end process;
```

<img width="480" alt="round_to_even.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/313464/c8d85975-fb7e-f3c5-5cd6-d99115f26249.png">
わかりにくいですが、0捨1入にあったバイアスが消えています。


また、Xilinx FPGAのDSPブロックをフルパフォーマンスで推論するような実装が
[(pdf) Vivado Design Suite ユーザー ガイド: 合成 (UG901) - Xilinx](https://www.xilinx.com/support/documentation/sw_manuals_j/xilinx2018_2/ug901-vivado-synthesis.pdf)の中で公開されています。

# 参考
[Gisselquist Technology, LCC - Rounding Numbers without Adding a Bias](https://zipcpu.com/dsp/2017/07/22/rounding.html) : 元ネタ、内容が若干怪しい
[Wikipedia - 端数処理](https://ja.wikipedia.org/wiki/%E7%AB%AF%E6%95%B0%E5%87%A6%E7%90%86#%E4%BA%94%E6%8D%A8%E4%BA%94%E8%B6%85%E5%85%A5)
[(pdf) Vivado Design Suite ユーザー ガイド: 合成 (UG901) - Xilinx](https://www.xilinx.com/support/documentation/sw_manuals_j/xilinx2018_2/ug901-vivado-synthesis.pdf)