# Median Filter FSM Modelling

I'm trying to build a median filter in Verilog using a comparator to sort out the highest pixel value and erase it, then sort out the next highest etc. until I have only 5 pixels left (I'm treating groups of 9 pixels) and the highest value of those is the median. I modelled this problem by having a initial state, one state to receive pixels and 5 states to find max. (Each state sorts between less bytes so at the end of my fifth state I'll have the median). Both code snippet below shows what I described above. Sorting module:

module MED #(parameter WIDTH = 8,
parameter NUM = 9)
(input [WIDTH-1:0]DI,
input DSI, BYP, CLK,
output [WIDTH-1:0] DO);

logic [WIDTH-1:0] R[0:NUM-1];
wire [WIDTH-1:0]MIN, MAX;
wire [WIDTH-1:0]D1, D2;

MCE #(.WIDTH(WIDTH)) MCE1(
.A(DO),
.B(R[NUM-2]),
.MIN(MIN),
.MAX(MAX)

);
assign D2 = (BYP) ? R[NUM-2] : MAX;
assign D1 = (DSI) ? DI : MIN;
assign DO = R[NUM-1];

always_ff @(posedge CLK)
begin
R <= {D1, R[0:NUM-2]};

R[NUM-1] <= D2;
end

endmodule


Whole filter:

module MEDIAN #(parameter WIDTH = 8)
(input [WIDTH-1:0]DI,
input DSI, nRST, CLK,
output [WIDTH-1:0] DO,
output logic DSO);

logic BYP;

MED #(.WIDTH(WIDTH), .NUM(9)) MED1(
.DI(DI),
.DSI(DSI),
.CLK(CLK),
.BYP(BYP),
.DO(DO)
);

//Compteur mod 8
//Le clk de sortie sera utilisé par la machine à états finis.
logic [3:0]counter;

always_ff @(posedge CLK or negedge nRST)
begin
if(!nRST)
counter <= 4'd0;

else if(counter == 4'b1000)
counter <= 4'd0;

else
counter <=counter+1;
end

//Machine à états finis

logic [2:0] state;
localparam INIT = 3'd0;
localparam S0 = 3'd1;
localparam S1 = 3'd2;
localparam S2 = 3'd3;
localparam S3 = 3'd4;
localparam S4 = 3'd5;
localparam S5 = 3'd6;

always_ff @(posedge CLK or negedge nRST)
begin

if(!nRST)
state <= INIT;
else
case(state)
INIT: if(DSI)
begin
counter <= 4'd0;
state <= S0;
end

S0  : if(counter == 4'd8)
begin
counter <= 4'd0;
state <= S1;
end

S1  : if(counter == 4'd8)
state <= S2;

S2  : if(counter == 4'd8)
state <= S3;

S3  : if(counter == 4'd8)
state <= S4;

S4  : if(counter == 4'd8)
state <= S5;

S5  :
state <= INIT;
endcase

end

always_comb
begin
if(state == INIT)
DSO = 0;

else if(state == S0)
BYP = 1;
if(counter == 8)
BYP = 0;

else if(state == S1)
BYP = (counter == 4'd8) ? 1 : 0;

else if(state == S2)
BYP = (counter > 4'd6) ? 1 : 0;

else if(state == S3)
BYP = (counter > 4'd5) ? 1 : 0;

else if(state == S4)
BYP = (counter > 4'd4) ? 1 : 0;

else if(state == S5)
begin
BYP = 0;
DSO = 1;
end
end

endmodule


This is the waveform I'm getting. Top row are my pixel values, bottom row is my current state and above that is my counter. Above the counter is my bypass signal, which would erase the max value and proceed to sort the next highest. What I wanted to have is have bypass set for when I have counter = 8 and state 2, then bypass set for counter = 7 and 8 when in state 3... Is there any way to fix this or should I model my FSM differently (I'd like to keep the principle of sorting by highest value and erasing them, though).

This looks like a mistake:

    else if(state == S0)
BYP = 1;
if(counter == 8)
BYP = 0;


Note that the else that follows this gets matched up with the second if, not the first one!

A begin/end pair would fix this, but based on the indentation and the general structure of that block, you probably wanted something more like:

    else if (state == S0)
BYP = (counter == 4'd8) ? 0 : 1;

• Thank you Dave! That does the trick of having my bypass signal placed in the right count as I described above. However, I still have problems showing the median. It seems the number 0x24 gets lost in the middle of the sorting process and never shows up again... It seems my bypass signal might last too long when it is supposed to be one pulse and I end up erasing more than one value. – Gabriel Ribeiro Dec 7 '19 at 2:58

More some notes than answers (but to long to be just comments) - what is a bit strang is that you have two always blocks which assign to counter. The first block does the counting while the following block in FSM actually write to counter sometimes as well. E.g. here:

S0  : if(counter == 4'd8)
begin
counter <= 4'd0;
state <= S1;
end


Furthermore is you counter counting to 8 which implies it actually is counter modulo 9 if I am not mistaken while your comment says that it should be "mod 8". And in your always_comb block you sometimes use "==" and sometimes "<" to compare the counting variable with your "thresholds". Is that intended?

Sometimes simplifying the code can help to find the issue. If I am not mistaken one could transform your code like this (only from scratch without testing/debugging!):

module MEDIAN #(parameter WIDTH = 8)
(input [WIDTH-1:0]DI,
input DSI, nRST, CLK,
output [WIDTH-1:0] DO,
output logic DSO);

logic BYP;

MED #(.WIDTH(WIDTH), .NUM(9)) MED1(
.DI(DI),
.DSI(DSI),
.CLK(CLK),
.BYP(BYP),
.DO(DO)
);

//Machine à états finis

logic [2:0] counter;
logic [2:0] state;
localparam INIT = 3'd0;
localparam S0 = 3'd1;
localparam S1 = 3'd2;
localparam S2 = 3'd3;
localparam S3 = 3'd4;
localparam S4 = 3'd5;
localparam S5 = 3'd6;

always_ff @(posedge CLK or negedge nRST)
begin

if(!nRST)
state   <= INIT;
counter <= 3'd0;
else
counter <= DSI ? 3'd0 : counter+1;

if(state == INIT)     state <= DSI ? S0 : INIT;
else if(state == S5)  state <= INIT;
else                  state <= state + (counter == 4'd8);
end

always_comb
begin
case(state)
INIT:    {BYP, DSO} = 2'b00;
S0  :    {BYP, DSO} = (counter == 4'd8) ? 2'b00 : 2'b10;
S1  :    {BYP, DSO} = (counter == 4'd8) ? 2'b00 : 2'b10;
S2  :    {BYP, DSO} = (counter == 4'd6) ? 2'b00 : 2'b10;
S3  :    {BYP, DSO} = (counter == 4'd5) ? 2'b00 : 2'b10;
S4  :    {BYP, DSO} = (counter == 4'd4) ? 2'b00 : 2'b10;
S5  :    {BYP, DSO} = 2'b01;
default: {BYP, DSO} = 2'b00;
endcase
end


Maybe you can use this as an inspiration. There is still some redundancy in this example. My personal recommendation is to avoid writing to a variable from blocks and to thread "cases" as multiplexer: assign a valid value for each case to each variable they "write to".