8bit Binary to BCD

Double dabble 이라는 알고리즘이 있다.

 

Double dabble 알고리즘은 아래와 같은 과정을 반복하여 2진수를 10진수로 변환한다.

 

1. 입력된 2진수를 1bit left shift한다.

2. 입력의 비트 크기만큼 shift를 하게 되면, 1, 10, 100, 1000, ... 의 column에 있는 숫자들로 BCD 코드를 출력. 그 외의 경우 과정 3을 진행한다.

3. 각 column의 값이 5 이상일 경우 각 column에 3을 더해준다.

4. 과정 1부터 다시 실행한다.

 

알고리즘 설명은 여기까지 하고, 이제 해당 알고리즘을 베릴로그 상에서 구현하는 방법을 생각해보자.

 

1) 우선 left shift를 했을 때 값을 hold 할 register가 필요해 보인다. 따라서 register를 컨트롤할 clock 신호 및 초기화를 위한 reset 신호가 필요할 것이다. 8비트 BCD의 경우 8비트는 255까지의 값을 나타내므로 1, 10, 100의 자리에 대해 각각 4비트씩의 register가 필요할 것이다. 더불어 기존의 2진수 입력 값 또한 hold 해야 하므로 8비트 BCD의 경우 8비트 register가 추가로 필요할 것이다. 즉 총 20비트의 레지스터가 필요할 것이다.

 

2) 그다음으로는 값을 left shift 해야 한다. 이는 각 레지스터를 concatenation을 통해 각 클락마다 변하도록 하면 해결될 것이다.

 

3) 각 레지스터의 값 중 하나라도 5 이상일 경우 left shift를 멈추고 3을 더해줘야 한다. 다만 덧셈 후에는 left shift를 무조건 해야 하므로 이를 컨트롤하는 변수가 필요할 것이다.

 

4) 총 8번의 left shift가 수행되어야 한다. 즉 0~7까지의 카운터가 필요하다.

 

1), 2), 3), 4)를 통해 이제 코딩을 해보자. 왜 이렇게 짰는지도 설명하겠다.

 

module bcd_8b(
    input [7:0] data_in,
    input clk, rst, bcd_en,
    output [11:0] data_out, 
    output EOF
);

reg [3:0] unit, ten, hundred;
reg [7:0] data_reg;
reg [2:0] count;
reg rEOF, rSOF; // register End of Func, register Start of Func
reg is_over_5_pass;

wire is_over_5_unit;
wire is_over_5_ten;
// wire is_over_5_hundred; 
// only unit and ten has value over 5
wire is_over_5;

assign is_over_5_unit    = ( unit[2] & (|unit[1:0]) ) | unit[3];
assign is_over_5_ten     = ( ten[2]  & (|ten[1:0])  ) | ten[3];
// assign is_over_5_hundred = ( hundred[2] & (|hundred[1:0]) ) | hundred[3];
assign is_over_5         = is_over_5_unit | is_over_5_ten;

assign EOF = rEOF;

assign data_out = rEOF ? {hundred, ten, unit} : 12'b0;

always @ (posedge clk) begin
    if (rst) begin
        unit <= 4'b0;
        ten <= 4'b0;
        hundred <= 4'b0;
        data_reg <= 8'b0;
        count <= 3'b0;
        rEOF <= 1'b0;
        rSOF <= 1'b0;
        is_over_5_pass <= 1'b0;
    end
    else if (rEOF) begin
        rSOF <= 1'b0;
        rEOF <= 1'b0;
    end
    else if (rSOF) begin
        if (is_over_5 & ~is_over_5_pass) begin
            if (is_over_5_unit) begin
                unit <= unit + 4'd3;
            end

            if (is_over_5_ten) begin
                ten <= ten + 4'd3;
            end
            is_over_5_pass <= is_over_5;
        end
        else begin
            is_over_5_pass <= 1'b0;
            hundred  <= {hundred[0 +: 3], ten[3]};
            ten      <= {ten[0 +: 3],     unit[3]};
            unit     <= {unit[0 +: 3],    data_reg[7]};
            data_reg <= {data_reg[0 +: 7], 1'b0};
            if (count == 3'd7) begin
                rEOF <= 1'b1;
                count <= 3'b0;
            end
            else begin
                count <= count + 3'b1;
            end
        end
    end
    else begin
        rSOF <= bcd_en;
        if (bcd_en) begin
            data_reg <= data_in;
            unit <= 4'b0;
            ten <= 4'b0;
            hundred <= 4'b0;
            is_over_5_pass <= 1'b0;
        end
    end
end

endmodule

 

여러 기능을 추가하다 보니 코드가 복잡해졌다. 하나하나 살펴보자.

 

입력과 출력은 각각 8비트, 12비트이다. EOF는 End Of Function을 줄인 말이다. 출력은 rEOF가 1일 경우를 제외하고 전부 0이 되도록 처리하였다. data_out은 {hundred, ten, unit}으로 wiring이 되었기 때문에 변환 도중에도 출력이 생기게 되는데, 이런 잘못된 출력을 내놓지 않기 위해 rEOF를 조건으로 뒀다.

 

is_over_5 변수는 레지스터 unit, ten의 값이 하나라도 5 이상일 경우에 1이 되도록 하였으며, is_over_5_pass는 5 이상인 값이 연속으로 나오게 될 경우 left shift를 할지 3을 더할지를 결정해주기 위해 추가하였다. 8비트 bcd의 경우 백의 자리 수는 3을 넘지 못하므로 주석 처리했다.

 

이제 always문 안을 살펴보자.

우선 리셋을 통해 모든 레지스터들의 값을 0으로 초기화한다. 참고로 pre-layout 시뮬레이션의 경우 flip-flop의 모든 비트를 0으로 초기화해야 제대로 작동한다. 리셋 조건에서는 1로 초기화하는 것을 주의해야 한다.

 

rEOF가 1이 될 경우 rEOF와 rSOF를 둘 다 0으로 초기화하여 bcd 모듈을 멈추게 하였다. 여기서 SOF는 Start Of Function의 줄임말이다. EOF나 SOF는 그냥 임의로 줄인 말이다. 널리 쓰이는 단어는 아닐 것 같다. EOF는 보통 End Of File로 쓰인다.

 

rSOF가 1이 될 경우에 binary to bcd converter가 동작하게 된다. 우선 pass를 is_5_over보다 한 클락 지연되도록 하여 덧셈이 연속적으로 일어나지 않도록 하였다. else 부분에서 left shift를 하게 되며, 카운터 또한 left shift 할 때만 증가하도록 하였다. 카운터가 0으로 초기화될 경우에 rEOF를 1로 만들어 동작을 멈추게 했다.

 

마지막 else문은 bcd converter가 작동을 시작할 때 레지스터들에 알맞은 값을 초기화하도록 구현했다.

 

만약에 다른 비트수의 bcd converter를 설계해야 한다면 바꿔야 할 부분은 총 3가지다.

1. 1, 10, 100, 1000,... 의 레지스터(4비트씩)

2. 카운터의 최댓값

3. 전체적인 비트 사이즈