Combinational circuit for sorting the string, Computer Engineering

Assignment Help:

Every input line of combinational circuit represents a specific element of the string let's say xi and every output line results in the form of a sorted list. In order to get the above mentioned task a comparator is used for the processing.  

Every comparator has two input lines suppose a and b, and likewise two output lines say c and d. Every comparator offers two outputs it implies that c provides maximum of a and b (max (a, b)) and d offers minimum of a and b (min (a, b)) in comparator InC and DeC it is opposite as displayed in Figures. 

In broad there are 2 types of comparators generally known as increasing comparators and decreasing comparators signified by + BM(n) and - BM(n) where n signifies the number of input lines and output lines of the comparator. The depth of + BM (n) and - BM (n) is log n. These comparators are used for constructing the circuit of sorting.

1905_COMBINATIONAL CIRCUIT FOR SORTING THE STRING.png

Figure: Increasing Comparator, for 2 inputs

1439_COMBINATIONAL CIRCUIT FOR SORTING THE STRING1.png

Figure: Decreasing Comparator, for 2 inputs

280_COMBINATIONAL CIRCUIT FOR SORTING THE STRING2.png

Figure: Increasing Comparator, for n inputs

772_COMBINATIONAL CIRCUIT FOR SORTING THE STRING3.png

Figure: Decreasing Comparator, for n inputs

Now let's suppose a famous sequence called bitonic sequence and sort out the elements employing a combinational circuit comprising a set of comparators. The property of bitonic sequence is in this manner: 

Consider a sequence X= x0, x1, x2, x3, x4 ......xn-1 such that state/condition 1: either x0, x1, x2, x3, x4 .......... xi is a monotonically increasing sequence and xi+1, xi+2,  ................ xn-1  is a monotonically decreasing sequence or state 2: there exists a cyclic shift of sequence  x0, x1, x2, x3, x4 ................... xn-1 such that resulting sequence satisfies the state 1.

Let's take a few illustrations of bitonic sequence: 

B1= 4,7,8,9,11,6,3,2,1 is bitonic sequence

B2= 12,15,17,18,19,11,8,7,6,4,5 is bitonic sequence

In order to give a solution to such a bitonic sequence different stages of comparators are needed. The fundamental approach followed for solving such a problem is as given:

Let's say we have a bitonic sequence X= x0, x1, x2, x3, x4 .......... xn-1 with the property that first n/2 elements are monotonically increasing elements are monotonically increasing such that x0< x1< x2< x3< x4...n/2-1 and other numbers are monotonically decreasing like xn/2> xn/2+1> ...>xn-1. Afterwards these patterns are weighed against with the help of a comparator in this manner:

 Y= min(x0, xn/2), min(x1, xn/2+1), min(x2, xn/2+2), ...........Min (xn/2-1, xn-1)

 Z= max(x0, xn/2), max (x1, xn/2+1), max (x2, xn/2+2), ........Max (xn/2-1, xn-1) 

After the above considered iteration, the two new bitonic sequences are generated and the method is known as bitonic split. Thenafter a recursive operation on these two bitonic sequences is processed until we are able to achieve the sorted list of elements. The accurate algorithm for sorting the bitonic sequence is as follows:

Sort_Bitonic (X)

// Input: N Numbers following the bitonic property

// Output: Sorted List of numbers

1) The Sequence which means that X is transmitted on the input lines of combinational circuit that consists of different set of comparators.

2) The sequence X is divided into two sub-bitonic sequences let's say Y and Z with the help of a process called bitonic split.

3) Recursively executes the bitonic divide on sub sequences which means that Y and Z till the size of subsequence reach to a level of 1.

4) The sorted sequence is attained after this phase on the output lines.


Related Discussions:- Combinational circuit for sorting the string

Explain logical shift micro-operations, Q. Explain logical shift Micro-oper...

Q. Explain logical shift Micro-operations? In logical shift data entering by serial input to left most or right most flip-flop (which depends on right or left shift operations

Overcoming global issues in e-commerce, E-commerce advance tremendous chanc...

E-commerce advance tremendous chance by permitting industrialist to buy Materials at a low price internationally. Also they give companies the opportunity to sell to universal stor

Exponential search, Exponential Search Another alternative to variable ...

Exponential Search Another alternative to variable size decrease-and-conquer search is known as exponential search. This algorithm begins searching at the beginning of the list

Provide a diagrammatic interpretation of the hardware stack, a) Prototype ...

a) Prototype a macro known AP which takes 4 integer parameters n (number of terms), a (first term), l (last term) and Sum (sum of n terms), provided that: Sum = (a+l)*n/2 b)

Display methods, Describe a console application project to show the differe...

Describe a console application project to show the different formatting styles used in display methods(i.e.Console.writeLine()).

Write examples of declarations of external variables, Examples of declarati...

Examples of declarations of external variables  that  are  not definitions: extern char stack[10]; extern int stkptr; These declarations tell the compiler that the variab

What is knowledge representation and reasoning, Artificial Intelligence Kno...

Artificial Intelligence Knowledge show (KR) is an area of artificial intelligence research aimed at showing knowledge in symbols to facilitate inferrencing from those knowledge ele

Explain the sum of product form - standard forms, Explain the Sum of Produc...

Explain the Sum of Product Form? In The Boolean Algebra a product is produced by "ANDing" two or more variable inputs. Product of the two variables is expressed as AB and three

Write Your Message!

Captcha
Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd