Abstract:
A circuit for coding a binary number represented in two&#39;s complement in a CSD-code wherein it is impossible for two immediately adjacent binary digits to respectively exhibit a &#34;1&#34;. The circuit is simply constructed and has a high operating speed. This is achieved by means of a series of logic components which respectively evaluate according to an exclusive-OR function and which create an output bit -1 from two respectively adjacent binary digits of the number to be encoded upon appearance of the bit combination 1,0. A series of second logic components create a CSD-coded bit combination 0, 1 from two respectively adjacent first logic components having the output bits 1,-1, but which accept the output bits of the remaining first logic components into the CSD-coded bit combination in unaltered fashion. The circuit is used in signal processors.

Description:
BACKGROUND OF THE INVENTION 
     The invention relates to a circuit for CSD-coding of a binary number represented in two&#39;s complement. 
     What is meant by a CSD-code (Canonical-Signed-Digit-Code) is a binary code in which it is impossible for two neighboring binary digits to each have a respective binary &#34;1&#34;. This means that so-called &#34;1&#34; blocks are missing in such a binary representation. It can be derived from the periodical &#34;IEEE Transactions on Acoustics, Speech and Signal Processing&#34;, Vol. ASSP-24, No. 1, February 1976, pages 76-86, incorporated herein by reference, that the CSD-code is primarily employed in digital data processing, particularly for the representation of multipliers, since every &#34;1&#34; bit of such a multiplier denotes an addition or subtraction operation depending on its operational sign. The number of these operations should be kept as low as possible. While about N/2 &#34;1&#34; bits occur on the average given a general binary code of an N-digit number, the average number of such signals is reduced to about N/3 given a CSD code. 
     SUMMARY OF THE INVENTION 
     An object of the invention is to specify a circuit for CSD coding of binary numbers wherein the circuit is simply constructed and assures the highest possible operating speed. This is achieved by providing at an input side a plurality of first logic means each having first and second inputs and first and second outputs. One of the first logic means has its first input connected to a given logic level and its second input connected to one of the bits of the binary number. A remainder of the first logic means each have their first and second inputs connected to mutually adjacent binary digit pairs of the binary number being encoded. Each of the first logic means provides at its first output a value bit derived from its two inputs according to an exclusive OR function. Each of the first logic means derives at its second output an operational sign bit comprising a logical &#34;1&#34; only when a higher order of the two bits at the two inputs comprises a logical &#34;1&#34; and a lower-order of the two bits comprises a logical &#34;0&#34;. A plurality of second logic means provide at their respective first and second outputs a CSD-coded bit combination of the input binary number. A pair of the second logic means derives a CSD-coded bit combination &#34;0,1&#34; at their outputs wherein an associated pair of first logic means to which they connect output a bit combination &#34;1,-1&#34;. An operational sign bit at the second output of a higher-order of the associated pair of first logic means is &#34;0&#34;  and its value bit at its first output is &#34;1&#34;. An operational sign bit at the second output of a lower-order of the associated pair of first logic means is &#34;1&#34; and its value bit at the first output is &#34;1&#34;. Bit combinations at the outputs of all of the remaining first logic means are transferred in unaltered fashion to the outputs of the second logic means as the CSD-coded bit combinations. 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS 
     The drawing is a schematic illustration of the circuit for CSD-coding of a binary number representing in two&#39;s complement according to the invention. 
    
    
     DESCRIPTION OF THE PREFERRED EMBODIMENTS 
     The inputs of the circuit according to the invention are referenced EO through EN. The bits x 0 , x 1  . . . x n  of a binary number are respectively supplied to the inputs, whereby x 0  indicates the lowest-order bit and x N  indicates the highest-order bit. Two of these inputs which are immediately adjacent to one another are connected to the two inputs of a logic component. In the drawing, for example, the circuit inputs E0 and E1 are interconnected to the inputs 1 and 2 of the logic component LS1, the circuit inputs E1 and E2 are connected to the inputs 3 and 4 of the logic component LS2, etc. The circuit inputs E(n-1) and EN lie at the inputs of the logic component LSN, whereas the circuit input E0 together with a further circuit input E&#39; that is constantly wired with a &#34;0&#34; is conducted to the input of the logic component LS0. 
     Of the logic components LS0 through LSN which are all designed identically, only LS1 shall be described in greater detail below. As can be seen from the drawing, the inputs 1,2 of LS1 are connected to two inputs of an exclusive OR element 5 whose output represents the first output 6 of LS1. Furthermore, input 2 which is occupied with the higher-order bit x 1  (1, of course, is associated with x 0 ) is connected to the first input of an AND element 7 whose second input is applied to the output of OR gate 5. The output of the AND element 7 forms the second output 8 of LS1. A value bit y v ,1 that is derived from the two bits x 0  and x 1  of the input side can be taken at the output 8, whereas an operational sign bit y s ,1 that is allocated to the value bit y v ,1 appears at the output 8. y s ,1 =0 thus denotes a positive operational sign, whereas y s ,1 =1 represents a negative operational sign. The value bits y v ,0, Y v ,2 . . . y v ,N to which further operational sign bits y s ,0, y s ,2 . . . y s ,N are allocated are derived from the respective bit pairs (&#34;0&#34;, x 0 ), (x 1 ,x x ) . . . (x N-1 ,x N ) of the input side via the other logic components LS0, LS2 . . . LSN in the same manner. 
     Each of the logic components LS0 through LSN has a further logic component LS0&#39; through LSN&#39; allocated to it, whereby the latter are again identically designed, so that only one of them, for example LS1&#39;, shall be described in greater detail below. LS1&#39; comprises four inputs 9 through 12, the inputs 10 and 11 thereof being interconnected to the outputs 8 and 6 of LS1. The input 9 is connected to the output 13 of LS2 which is provided for the value bit y v ,2, whereas the input 12 is conducted to the output 14 of LS0, said output 14 being provided for the operational sign bit y s ,0. The input 9 is also connected via an inverter to the first input of an AND element 15, whereby said inverter can, as shown, be incorporated into the element 15, whereas the input 10 is wired to the second input of the AND element 15. The input 11 of LS1&#39; is connected to the first input of an AND element 16, whereby the input 12 is conducted via an inverter to the second input of 16. In the drawing, this inverter has again been incorporated into the element 16, whereby the corresponding input of 16 is shown as an inverting input. The outputs of the AND elements 15 and 16 respectively form the outputs A12 and A11 of the further logic component LS1&#39;. 
     A value bit z v ,1 that appears at the output A11 is derived from the quantities y s ,1 and y v ,1 as well as y v ,2 and y v ,0 via LS1&#39;. An operational sign bit z s ,1 that can be obtained at the output A12 belongs to the value bit and is likewise derived from the quantities y s ,1 and y v ,1. Corresponding value bits z v ,0, z v ,2 . . . z v ,N that are respectively available at the outputs A01, A21 . . . , AN1 as well as corresponding operational sign bits z s ,0, z s ,2 . . . z s ,N that appear at the outputs A02, A22 . . . AN2 are derived in an analogous manner via the further logic components LS0&#39;, LS2&#39; . . . LSN&#39;. 
     In general, two of the four inputs in each of the further logic components LS0&#39; . . . LSN&#39; are connected to the two outputs of the corresponding logic component LS0 . . . LSN, whereas a third input is wired to the value output of the logic component of the next-higher order that is immediately adjacent to the corresponding logic component and the fourth input is wired to the operational sign output of the logic component of the next-lower order that is immediately adjacent to the corresponding logic component. The fourth input 17 of the further logic component LS0&#39; is connected to a circuit input E&#34; that is constantly connected with a &#34;0&#34;, whereas the third input 18 of LSN&#39; is wired to a further circuit input E&#39;&#34; that is constantly connected with a &#34;0&#34;. The bit combination z v ,0, z s ,0 . . . z v ,N, z s ,N that is tappable at the outputs A01 through AN2 represents the CSD-coded binary output signal of the circuit that has been derived from the number x 0  . . . x N  present at the input side. 
     It is of essential significance to the functioning of the circuit that each of the logic components LS0 . . . LSN, for example the element LS1, emits a logical &#34;1&#34; at its value output, for example 6, only when different bits are present at its inputs. Furthermore, a &#34;1&#34; only appears at the corresponding operational sign output, for example 8, of the logic component under consideration when the input bit of higher-order for example x 1 , consists of a logical &#34;1&#34; but the lower-order input bit, for example x 0 , consists of a logical &#34;0&#34;. Thus only in this case is a negative operational sign assigned to the value bit &#34;1&#34; at the output, for example 6, of the logic component under consideration. 
     For x 0  =0 and x 1  =1, for example, the signals y v ,1 -1 and y s ,1 =1 result. When it is further assumed that x 2  =-, then the signals y v ,2 =1 and y s ,2 -0 result at the outputs of LS2. Thus, two logic components lying next to one another, namely LS2 and LS1, have an operational-sign affected output-side bit combination 1,-1 so that the higher-order logic component, namely LS2, is cited first. The further logic components allocated to LS2 and LS1, namely LS2&#39; and LS1&#39; result in a CSD-coded bit combination 0,1 only from this bit combination. This corresponds in detail to the following output signals: z v ,1 =1, z s ,1 =0, z v ,2 =0 and z s ,2 =0. It is presumed that the operational sign bit is y s ,0 =0. This, however, derives from the above assumption that x 0  =0. When the remaining logic components, i.e. LS0, LS3 . . . LSN exhibit no such bit combinations at the output side when considered in pairs, then their bit combinations, i.e. the signals y v ,0, y s ,0, y v ,3 . . . y v ,N, y z ,N are transmitted unaltered into corresponding signals at the outputs of the further logic components, i.e. z v ,0, z s ,0, z v ,3, z s ,3 . . . z v ,N, z s ,N. 
     When one considers the function of a further logic component, for example LS1&#39;, then one can see that a CSD-coded value bit z v ,1 can be tapped at its value output A11, the value bit corresponding to the value bit y v ,1 supplied from the allocated logic component when the operational sign bit y s ,0 supplied from the neighboring, lower-order logic component consists of a logical &#34;0&#34;. Otherwise, the input-side value bit y v ,1 is negated when the operational sign bit y s ,0 consists of a logical &#34;1&#34;. A CSD-coded operational sign bit z s ,1 can be obtained at the operational sign output A12 of the further logic component LS1&#39;, said CSD-coded operational sign bit corresponding to the operational sign bit y s ,1 supplied from the corresponding logic component when the value bit y v ,2 supplied from the neighboring, higher-order logic component consists of a logical &#34;0&#34;, whereas a logical &#34;1&#34; of this value bit leads to a negation of the supplied operational sign bit y s ,1. The function of the logic components LS0&#39;, LS2&#39; . . . LSN&#39; is analogous to the function of LS1&#39; described above. 
     Although various minor changes and modifications might be proposed by those skilled in the art, it will be understood that I wish to include within the claims of the patent warranted hereon all such changes and modifications as reasonably come within my contribution to the art.