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 the differences between paging and segmentation, Explain the differ...

Explain the differences between Paging and segmentation. Paging and segmentation P aging Segmentation Computer memory is separa

What is input - output commands, Q. What is Input - Output commands? Th...

Q. What is Input - Output commands? There are four kinds of I/O commands which an I/O interface can receive when it's addressed by a processor: Control : This type of c

Basic performance equation, Explain the basic performance equation Ans...

Explain the basic performance equation Ans: The basic performance equation is following T = N * S/ R T =>  It is processor time required to execute a program N => act

How music is produced and generated - cad, How music is produced and genera...

How music is produced and generated - CAD Computer software and hardware advances have changed how music is produced and generated. Some of the primary reasons for this have

Explain the techniques used for protection of user files, Explain the techn...

Explain the techniques used for protection of user files. This is easier to protect against accidental than malicious misuse. Protection of user files implies that file owne

IA-32 support, In order to support IA-32 Itanium can switch in 32-bit mode ...

In order to support IA-32 Itanium can switch in 32-bit mode with special jump escape instructions. IA-32 instructions have been mapped to Itanium's functional units. But as Itanium

Layered architecture.., advantages and disadvantages of layered architectur...

advantages and disadvantages of layered architecture in computer network.

How do you turn off cookies for one page in your site, How do you turn off ...

How do you turn off cookies for one page in your site?  Use the Cookie. Discard Property which Gets or sets the discard flag set by the server. When true, this property initiat

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