A Sorting Circuit in Digital Logic Design

Hello; I am trying to implement a Linear Array Sort that takes in 10 8-bit inputs serially snd outputs the inputs in increasing order. I figured out that Bubble Sort is the easiest kind of sort that can be implemented in hardware. The first step to implement this Linear Array Sorter was to read in the inputs. I used a Modulo 10 counter to read in the inputs from the user. Now how can I continue from here? I thought that using a 1-bit comparator (1-bit slicing) can work. But I then realized that I need buffers and other counters for further implementaion. Please, any ideas? I would really appreciate your help. Thanks.

Reply to
Johnathan Coll
Loading thread data ...

What are you options for implementing the functionality? It's trivial in a microcontroller, somewhat time consuming but not difficult in a CPLD/FPGA, but potentially quite time consuming (hours) if you have to do it in "jellybean" logic (74xx/40xx series ICs).

Since this sounds like a somewaht contrived exercise (e.g., a homework problem), about the simplest/crudest way I can think to do this is as follows: Use a 256x1 bit RAM; clear all of it to start. When you receive an input, apply it to the RAM's address pins and set that bit to 1. Now, once all the words are received, just run through *all 256 addresses* of the RAM, and any time you hit a location that contain 1, shift out the current address. Poof! -- No sorting as such necessary.

Obvious this technique doesn't scale well -- it wouldn't work for, e.g., 64 bit numbers, and it has a drawback that any input received twice is only output once (if you really felt like it, you could get fancy and use a 256x3 bit RAM to keep track of how many times a word was received), but it should be adequate given how contrived the assignment sounds like in the first place.

---Joel

Reply to
Joel Kolstad

Perhaps not. Like so many of these questions, your specifications aren't exactly complete. For example, if your data is coming in MSB first, the first cycle you can output as many '1' on the high-order outputs as there are '1's on the inputs. Then look at 11's, 10's and 01's. Rinse and repeat. Optomizing this may take a bit of work but try to take advantage of the serial nature of your data.

Class project?

--
  Keith
Reply to
krw

No. I wish it was a class project. I am an unemployed VLSI technician. In Florida, VLSI is not very common. I have read this project while browsing the internet and I found it rather challenging.

I just thought to myself that setting my first goal to reading the inputs from the user and placing them in an array would be a nice move.

Well, I did place my 10 inputs that need to be sorted in registers using a counter as my FSM which sets the enables of the registers.

My next step now is to compare these numbers, find the maximum and bubble it to the bottom and eventaully sort the array. It is easy to use the term "Rinse", but I need practical implementations in hardware. Like how many counters am I supposed to use, how can i implement my FSM, how can i implement the RAM, .....

I have always used a-bit slicing in my designs. 1-bit slicing is like my blueprint, so I would prefer to use 1-bit slicing in this self-generated project as well. It is ok. If you guys find it difficult to help, no problem. I am sure I will find a solution eventaully, BUT i thought that starting such a topic on GOOGLE groups can be interesting.

My ultimate goal is to implement this Linear Array Sorter on Altera and then generate the layout on magic. So, it is pretty tedious to implement a RAM in VLSI starting from scratch.

Thanks a lot guys for your patience.

Reply to
Johnathan Coll

On a sunny day (26 Dec 2006 02:31:49 -0800) it happened "Johnathan Coll" wrote in :

Post again in comp.arch.fpga Can you do it is asm (bubble sort)? Antti just published a free program to translate asm to bitfile for many FPGAs there. Just wondering how fast it would be.. that uses microblaze processor HDL. So possibly a lot slower..... hehe. Clearly you need to store somewhere in memory, do compares, but make a list of addresses in a second memory. In case of bubble sort you have to run the list again and again until no change takes place. Maybe hashing is faster?

Reply to
Jan Panteltje

On a sunny day (Tue, 26 Dec 2006 11:12:56 GMT) it happened Jan Panteltje wrote in :

Oh, and there is binary tree too.

Reply to
Jan Panteltje

Even more challenging when all the requirements aren't stated. ;-)

It's the way you'd do it in a microcontroller, if you had all day to do the sort. Since you're doing the sort in hardware I expected some speed requirements, like a small latency from input to output.

If you're using FPGAs stay away from counters for FSMs (you haven't specified a design methodology either). FPGAs are latch-rich (you bought 'em - use 'em) so "one-hot" FSMs are almost always a win.

The devil is always in the details (which we have few).

Your compare should be able to be done serially. Your data is serial, so can the arithmetic.

Given the lack of detail it sounded like a class project. Many are reluctant to answer these.

I'm not familiar with Altera's products but Xilinx has RAMs, block- rams, FIFOs, shift-registers, and all that as primitives. You really need to get out of the microcontroller-think when designing hardware.

--
  Keith
Reply to
krw

Thanks a lot guys for your help.

If you want more details, I will give you details that I set.

I do not care about the timing. I just want to sort 10 digits each with

8 bits. I do not care about the input output latency. I want to generate FSM since i want to implement it from scratch on VLSI. I do not want to use FPGA's. Before starting the VLSI magic implementation and layout, I want to test my design on Altera. I do not care about the time it takes to sort as long as it outputs the data serially in the correct sorted order.

Thanks again.

Reply to
Johnathan Coll

Oowee, that sounds like a lot of fun.

If you want to bit slice, many large FPGAs that i have seem to favor 4 or 8 bit slices. It seems to have something to do with the underlying architecture of the FPGA.

As for the sorting algorithm, forget the bubble sort, it is inefficient in any implementation. For ten items, try a "shaker sort" or a "merge sort"; both guaranteed O(n*ln(n)) performance in time and hardware.

In general read up a bunch on sorting algorithms, it will help you a lot in any implementation you choose.

--
 JosephKK
 Gegen dummheit kampfen die Gotter Selbst, vergebens.  
 Click to see the full signature
Reply to
joseph2k

Shit, just throwing a uP core and some ram and rom at it is a poor calling card for a design. Besides, then you are usually tasked with providing all the software to run the chip and do the job. No escape there. For the design size requirements, you actually are much better off doing it directly in the FPGA.

--
 JosephKK
 Gegen dummheit kampfen die Gotter Selbst, vergebens.  
 Click to see the full signature
Reply to
joseph2k

ElectronDepot website is not affiliated with any of the manufacturers or service providers discussed here. All logos and trade names are the property of their respective owners.