Abstract:
A device for calculating the quotient q and remainder r of the division (y·k 1 +x)/k 2 , wherein k 1  and k 2  are integers and constant, and wherein x and y are integers. The device comprises a first digital circuit for receiving as input values of y and identifying corresponding values of the quotient q y  and the remainder r y  of the function y·k 1 /k 2 , a second digital circuit for calculating the remainder r of the division, by a) calculating a combined value (x+r y ) of the remainder r y  and the value of x, b) verifying if the combined value (x+r y ) is less than k 2 , c) correcting the combined value (x+r y ) if the verification indicates that the combined value (x+r y ) is not less than k 2 , and d) assigning the corrected combined value (x+r y ) to the remainder r, a third digital circuit for calculating the quotient q of the division, by a) correcting the quotient q y  if the verification ( 2206 ) indicates that the combined value (x+r y ) is not less than k 2 , and b) assigning the corrected quotient q y  to the quotient q.

Description:
FIELD OF THE INVENTION 
     The present description regards computation of quotients. The description has been developed with a view to its use for computing quotients during conversion of a logical-address space (for example, of a display) into a physical-address space and (for example, of a memory). 
     BACKGROUND OF THE INVENTION 
     Applications such as Systems On Chip (SoCs) or Application-Specific Integrated Circuits (ASICs) frequently use a function for mapping of the addresses of a memory to carry out a conversion from a logical-address space addresses to a physical-address space. 
     For example, specific applications may desire a predetermined logical-address space, such as logical rows and columns, which are defined during specification of the block. However, the physical-address space may be different on account of limitations during design of the chip layout. These may, for example, be limitations on the ratio between the width and the height of the memory, which is one of the significant factors during definition of the “floorplan” of the integrated circuit to enable determination of the total area of the integrated circuit. 
     To enable a re-use of one and the same block in various different applications, it is hence useful to develop a generic digital block (also referred to frequently as “Intellectual Property core” or “IP core”), which comprises a standard memory interface. In this case, an additional block is used, which is responsible for conversion of the logical addresses into real physical addresses. 
     For instance, a possible sphere of application can be a small drive unit for a display, where the drive unit has the task of reading the video data from a RAM for driving the respective pixels of the display. However, the ratio between the width and the height of the memory and of the display are not usually correlated. For example, the display may have a size of 220×176 pixels, while the memory has a size of 480×82. This is also highlighted in  FIG. 1 , which shows an example of mapping of a row R in the logical-address space LAS in a respective portion P into the physical-address space PAS. 
     In general, to enable a read and/or write access, the conversion block translates the logical address into the physical address of the memory with the following mathematical relations: 
                     q   ⁡     (     x   ,   y     )       =     quotient   ⁡     (         y   ·     k   1       +   x       k   2       )               (   1   )                 r   ⁡     (     x   ,   y     )       =     remainder   ⁡     (         y   ·     k   1       +   x       k   2       )               (   2   )               
where k 1  is the number of the (logical) columns of the display, k 2  is the number of the (physical) columns of the RAM, (x,y) is the location on the display (i.e., the logical address), and (q, r) is the location in the memory (i.e., the physical address), where q is the quotient, and r is the remainder of the division.
 
     The mathematical relation hence represents conversion from the two-dimensional space (x,y) into the two-dimensional space (q, r), i.e., translation of the logical space into the physical space. In general, the constants k 1  and k 2  can be any integer being greater than two. 
       FIG. 2  shows a block diagram of an example of possible implementation of Eqs. (1) and (2). In particular, provided in this implementation are a multiplier  102  and an adder  104  that compute the relation (y·k 1 +x). The result of the addition is sent to a block  106 , for example a divider, which yields the quotient q and the remainder r of the division (y·k 1 +x)/k 2 . 
     This circuit thus enables conversion of logical address by specifying the parameters k 1  and k 2 . This approach presents significant disadvantages in terms of performance (for example, in terms of maximum delay) and occupation of area of silicon, however. 
     It is likewise noted that, in some particular cases, it is possible to exploit the properties of the constant k 1  and k 2  to optimize the operations of multiplication and/or division at the bit level. For example, if the value of k 1  and/or k 2  is a multiple of 2, the operations of multiplication and/or division can be implemented via a simple shift operation. In particular cases, this behaviour can be exploited for implementing a dedicated “wrapper”, i.e., a combinational circuit, for example implemented within an ASIC, which enables direct conversion of a logical address into a physical address. 
     This is possible if there exists a simple relation between the constant k 1  and k 2  (for example, when k 1  is a multiple of k 2 ). However, in general these optimizations are not possible and, to speed up the circuit, there frequently remains the use of a structure of the pipeline type, which calls for a complex control structure and hence additional area of silicon. 
     SUMMARY OF THE INVENTION 
     The object of the invention is to provide an approach for the translation of logical addresses into physical addresses and that is generally applicable for any value of k 1  and k 2  and with improved performance (for example, in terms of occupation of area within an integrated circuit). 
     With a view to achieving the aforesaid purpose, the object of the invention is a device for computing the quotient q and remainder r of the division (y·k 1 +x)/k 2  that presents the characteristics specified in claim  1 . Further advantageous characteristics form the subject of the dependent claims. 
     In various embodiments, instead of a generic multiplier and a generic divider, functions of conversion that can be implemented via look-up tables (LUTs) or simple combinational circuits are present. In various embodiments, the conversion can be performed in two steps. 
     In a first step, the components x and y are considered independently and at least the component y is translated into the space (q, r), i.e., the number of the logical row y is translated into a logical address (q y , r y ). This step can be implemented by a static-conversion function determined via the constant k 1  and k 2 , i.e., the conversion function remains unaltered during normal operation of the circuit, and to the same input there corresponds the same output. 
     In an embodiment, also the component x, i.e., the number of the logical column x, is translated into a physical address (q x , r x ) in the space (q, r). In a second step, the intermediate result (q y , r y ) is combined with the number of the column x or the intermediate result (q x , r x ) to form the final result (q, r). For example, in an embodiment, the intermediate results (q x , r x ) and (q y , r y ) are added in a smart way, considering also the effective physical-address space, or else possible conditions of overflow or carry propagation may occur. 
     In an embodiment, the static tables for the functions of conversion of the components x and y are pre-computed starting from the constant k 1  and k 2 , through a high-level program (e.g., C, Matlab, Tcl, Perl, etc.) that encodes them with a description that can be synthesized and integrated with the block that implements the smart sum of the partial results, encoded with a hardware language (for example, VHDL, Verilog). 
     Various embodiments can be used, in general, whenever it is desired to compute the quotient q and remainder r of the division:
 
(y·k 1 +x)/k 2   (3)
 
where k 1  and k 2  are integers and constant, and where x and y are integers.
 
     In various embodiments, this approach can be integrated in software executed by a processor and used for the logical synthesis (i.e., translation of the HDL code into a circuit description), which recognizes Eq. (3) and implements the equation with one of the circuits described herein on the basis, for example, of the specific attributes of performance and/or occupation of area within the integrated circuit. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
       The invention will now be described, purely by way of non-limiting example, with reference to the annexed drawings, wherein: 
         FIGS. 1 and 2  represent the prior art; 
         FIGS. 3 to 5  show a first embodiment, in accordance with the present invention; and 
         FIGS. 6 and 7  show a second embodiment in accordance with the present invention. 
     
    
    
     DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS 
     In the ensuing description, various specific details are illustrated and aimed at providing an in-depth understanding of the embodiments. The embodiments can be obtained without one or more of the specific details, or with other methods, components, materials, etc. In other cases, well-known structures, materials, or operations are not illustrated or described in detail so as not to render various aspects of the embodiments obscure. 
     Reference to “an embodiment” or “one embodiment” in the framework of this description is aimed at indicating that a particular configuration, structure or characteristic described in relation to the embodiment is included in at least one embodiment. Hence, phrases such as “in an embodiment” or “in one embodiment” that may be present in different points of this description do not necessarily refer to one and the same embodiment. Furthermore, particular conformations, structures, or characteristics can be combined in an adequate way in one or more embodiments. 
     The references used herein are adopted purely for reasons of convenience and hence do not define the sphere of protection or the scope of the embodiments. 
     In general, the embodiments considered herein are based upon implementations of Eqs. (1) and (2), thus avoiding the use of complex arithmetical blocks. In fact, it is noted that, by exploiting the fact that the parameters k 1  and k 2  are constant, the conversion can be performed in two steps by rewriting Eq. (3) in the following way: 
     
       
         
           
             
               
                 
                   
                     f 
                     ⁡ 
                     
                       ( 
                       
                         x 
                         , 
                         y 
                       
                       ) 
                     
                   
                   = 
                   
                     
                       
                         y 
                         · 
                         
                           k 
                           1 
                         
                       
                       
                         k 
                         2 
                       
                     
                     + 
                     
                       x 
                       
                         k 
                         2 
                       
                     
                   
                 
               
               
                 
                   ( 
                   4 
                   ) 
                 
               
             
           
         
       
     
       FIG. 3  shows the general scheme of a possible embodiment of these two steps. In a first step  20 , each component is translated into the space (q, r), i.e., the component x is translated into an address (q x , r x ), and the component y is translated into an address (q y , r y ). This step can be implemented by a static-conversion function determined by the constants k 1  and k 2 ; i.e., the conversion function remains unaltered during normal operation of the circuit and to one and the same input there corresponds the same output. 
     In a second step  22 , these intermediate results (q x , r x ) and (q y , r y ) are combined to form the final result (q, r). For example, in an embodiment, these intermediate results (q x , r x ) and (q y , r y ) are summed up in a smart way by considering also the effective physical-address space or else possible conditions of overflow or carry propagation. 
     Instead of a multiplier and/or divider (which are circuits the function of which is intrinsically linked to at least two input data, i.e., at least two factors in the case of the multiplier, and dividend and divisor in the case of the divider) the circuit considered herein envisages functions of conversion of a tabular or combinational type, i.e., functions that can be implemented via look-up tables (LUTs) or simple combinational circuits that, at the circuit level, can be implemented so as to operate as a function of one input datum. 
     The approach is well suited also for a possible integration thereof within a program that generates, starting from the constant k 1  and k 2 , the description of the circuit, for example in a high-level language (HDL). 
       FIG. 4  shows an embodiment of a corresponding conversion circuit. In the embodiment considered, two conversion blocks  200   x  and  200   y  are envisaged, which translate the components x and y into the space (q, r). In particular, block  200   x  translates the component x into an address (q x , r x ), and block  200   y  translates the component y into an address (q y , r y ). 
     In an embodiment, the functions of conversion implemented within blocks  200   x  and  200   y  are pre-computed during modelling of the circuit. For example, a program can generate directly, starting from the parameters k 1  and k 2 , a synthesizable code, for example an HDL code (such as, for example, VERILOG or VHDL) or a logic table. Subsequently, this code can be synthesized for the desired architecture, for example an ASIC, an FPGA or a PLA. 
     As already anticipated, the conversion is based upon the quotient q and the remainder r of the following function: 
                       f   ⁡     (     x   ,   y     )       =         y   ·     k   1         k   2       +     x     k   2           ⁢     
     ⁢       i   .   e   .     ,             (   5   )                   y   ·     k   1       +   x     =       q   ·     k   2       +   r             (   6   )               
where Eq. (6) satisfies the congruence relation, where the remainder r is the least of the values that satisfy the relation
 
 y·k   1+x≡r (mod  k   2 ), 0 ≦r&lt;k   2   (7)
 
     The first term in Eq. (6) represents the transformation of the space (x, y) into a one-dimensional space; by separating the components x and y it is possible to rewrite the equation for the component y as follows: 
     
       
         
           
             
               
                 
                   
                     
                       y 
                       · 
                       
                         k 
                         1 
                       
                     
                     = 
                     
                       
                         
                           q 
                           y 
                         
                         · 
                         
                           k 
                           2 
                         
                       
                       + 
                       
                         r 
                         y 
                       
                     
                   
                   , 
                   
                     0 
                     ≤ 
                     
                       r 
                       y 
                     
                     &lt; 
                     
                       k 
                       2 
                     
                   
                 
               
               
                 
                   ( 
                   8 
                   ) 
                 
               
             
             
               
                 
                   
                     
                       y 
                       · 
                       
                         k 
                         1 
                       
                     
                     
                       k 
                       2 
                     
                   
                   -&gt; 
                   
                     ( 
                     
                       
                         q 
                         y 
                       
                       , 
                       
                         r 
                         y 
                       
                     
                     ) 
                   
                 
               
               
                 
                   ( 
                   9 
                   ) 
                 
               
             
           
         
       
     
     For the application considered herein by way of example, the physical address (q y , r y ), which represents the start of the logical row y in the physical-address space, is then computed. The conversion function that translates the component y on (q y , r y ) and that can be implemented within block  200   y  is thus based upon constant values and can be pre-computed. 
     In substantially the same way, we can also rewrite the contribution of the component x as follows: 
     
       
         
           
             
               
                 
                   
                     x 
                     = 
                     
                       
                         
                           q 
                           x 
                         
                         · 
                         
                           k 
                           2 
                         
                       
                       + 
                       
                         r 
                         x 
                       
                     
                   
                   , 
                   
                     0 
                     ≤ 
                     
                       r 
                       x 
                     
                     &lt; 
                     
                       k 
                       2 
                     
                   
                 
               
               
                 
                   ( 
                   10 
                   ) 
                 
               
             
             
               
                 
                   
                     x 
                     
                       k 
                       2 
                     
                   
                   -&gt; 
                   
                     ( 
                     
                       
                         q 
                         x 
                       
                       , 
                       
                         r 
                         x 
                       
                     
                     ) 
                   
                 
               
               
                 
                   ( 
                   11 
                   ) 
                 
               
             
           
         
       
     
     In the embodiment considered herein by way of example, Eq. (11) is implemented within block  200   x  by means of a second conversion function that translates the component x into (q x , r x ). 
     For the application considered herein by way of example, the physical address (q x , r x ), which represents the offset of the column x, is then computed. 
     In the embodiment considered, to determine the quotient q and the final remainder r (i.e., the final physical address), in block  220  the partial results (q x , r x ) and (q y , r y ) are added (i.e., the offset x and the start of the logical row y represented in the physical-address space). 
     In an embodiment, block  220  also takes into account, during computation of the final values q and r, the congruence relation of Eq. (7)
 
 y·k   1   +x =( q   y   +q   x )· k   2 +( r   y   +r   x )  (12)
 
where r y  and r x  are the partial remainders, and the final remainder r respects the congruence relation:
 
y·k 1 +x≡(r y +r x )mod k 2   (13)
 
     The sum (r y +r x ) may not always represent the minimum value that satisfies this criterion, because
 
0≦( r   y   +r   x )&lt;2 ·k   2   (14)
 
     In an embodiment, block  220  corrects the final result and implements the following equation: 
     
       
         
           
             
               
                 
                   
                     
                       
                         y 
                         · 
                         
                           k 
                           1 
                         
                       
                       + 
                       x 
                     
                     = 
                     
                       
                         
                           ( 
                           
                             
                               q 
                               y 
                             
                             + 
                             
                               q 
                               x 
                             
                             + 
                             
                               q 
                               adj 
                             
                           
                           ) 
                         
                         · 
                         
                           k 
                           2 
                         
                       
                       + 
                       r 
                     
                   
                   ⁢ 
                   
                     
 
                   
                   ⁢ 
                   where 
                 
               
               
                 
                   ( 
                   15 
                   ) 
                 
               
             
             
               
                 
                   
                     q 
                     adj 
                   
                   = 
                   
                     { 
                     
                       
                         
                           0 
                         
                         
                           
                             0 
                             ≤ 
                             
                               ( 
                               
                                 
                                   r 
                                   y 
                                 
                                 + 
                                 
                                   r 
                                   x 
                                 
                               
                               ) 
                             
                             &lt; 
                             
                               k 
                               2 
                             
                           
                         
                       
                       
                         
                           1 
                         
                         
                           
                             
                               k 
                               2 
                             
                             ≤ 
                             
                               ( 
                               
                                 
                                   r 
                                   y 
                                 
                                 + 
                                 
                                   r 
                                   x 
                                 
                               
                               ) 
                             
                             &lt; 
                             
                               2 
                               · 
                               
                                 k 
                                 2 
                               
                             
                           
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   16 
                   ) 
                 
               
             
             
               
                 
                   r 
                   = 
                   
                     { 
                     
                       
                         
                           
                             
                               ( 
                               
                                 
                                   r 
                                   y 
                                 
                                 + 
                                 
                                   r 
                                   x 
                                 
                               
                               ) 
                             
                             , 
                           
                         
                         
                           
                             0 
                             ≤ 
                             
                               ( 
                               
                                 
                                   r 
                                   y 
                                 
                                 + 
                                 
                                   r 
                                   x 
                                 
                               
                               ) 
                             
                             &lt; 
                             
                               k 
                               2 
                             
                           
                         
                       
                       
                         
                           
                             
                               ( 
                               
                                 
                                   r 
                                   y 
                                 
                                 + 
                                 
                                   r 
                                   x 
                                 
                                 - 
                                 
                                   k 
                                   2 
                                 
                               
                               ) 
                             
                             , 
                           
                         
                         
                           
                             
                               k 
                               2 
                             
                             ≤ 
                             
                               ( 
                               
                                 
                                   r 
                                   y 
                                 
                                 + 
                                 
                                   r 
                                   x 
                                 
                               
                               ) 
                             
                             &lt; 
                             
                               2 
                               · 
                               
                                 k 
                                 2 
                               
                             
                           
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   17 
                   ) 
                 
               
             
           
         
       
     
       FIG. 5  shows a block diagram of a possible embodiment that implements the conversion of the components x and y, and the combination of the partial results as illustrated in Eqs. (15) to (17). 
     In the embodiment considered, Eq. (11), i.e., the translation of the component x into the logical-address space (q x , r x ), is performed via block  200   x , which implements the function (1/k 2 ). 
     In an embodiment, block  200   x  is not a generic divider as used in the known art, but a digital circuit, for example a combinational circuit or a look-up table, which implements the function (1/k 2 ) for the specific value of k 2 . However, a generic divider could be used. Even though this choice is not usually preferable, in any case a reduction of the circuit complexity is obtained, because a division on a smaller number of bits is used. 
     In the embodiment considered, block  200   y  implements Eq. (9), i.e., the translation of the component y into the space (q y , r y ). Also in this case, block  200   y  can be implemented via a digital circuit, for example a combinational circuit or a look-up table, which implements the function (k 1 /k 2 ) only for the specific values of k 1  and k 2 . The partial results (q x , r x ) and (q y , r y ) are supplied to a block  220  for to form the final result (q, r). 
     In the embodiment considered, block  220  comprises an adder  2202  for computing the sum (r x +r y ) and an adder  2204  for computing the sum (q x +q y ). Next, a check is made to see whether these results are to be corrected as shown with reference to Eqs. (15) to (17). In particular, in the case where the sum (r x +r y ) is less than k 2 , the results (r x +r y ) and (q x +q y ) remain unaltered; otherwise, they are corrected. 
     In the embodiment considered, a comparator  2206  verifies whether the sum (r x +r y ) is less than k 2 . The result of the verification is given to two multiplexers  2208  and  2210 , which yield the respective correction values. 
     In the embodiment considered, the multiplexer  2208  supplies the value “0” or the value −k 2  to an adder  2212  for computing the final remainder r, and the multiplexer  2210  supplies the value “0” or the value “1” to an adder (incrementer)  2214  for computing the final quotient q. 
     The embodiment shown in  FIG. 5  thus comprises simple digital blocks, which enable reduction of occupation of area within the integrated circuit and/or improvement of the performance of the circuit. 
       FIG. 6  shows a second embodiment that does not use block  200   x  for conversion of the component x. In this embodiment, the component (i.e., the offset) x is combined directly with the partial remainder r y  within block  220 . 
     As shown with reference to Eq. (10), the partial remainder r x  can be computed as:
 
 r   x   =x −( q   x   ·k   2 )  (18)
 
     This means that the remainder r x  of the division (x/k 2 ) results from the subtraction of q x  times k 2  from the value of x, where the number of the possible values of q x  depends upon the ratio between the constant k 1  and k 2 , also referred to as column ratio in the case of conversion of physical and logical addresses:
 
 CR =quotient( k   1   /k   2 )
 
where k 1  is the maximum value of x, i.e., the number of the logical columns, and k 2  is the maximum value of r, i.e., the number of the physical columns. The ratio CR is typically less than 5-10.
 
     Starting from Eq. (8), we can thus write:
 
 y·k   1   +x =( q   y   ·k   2   +r   y )+ x   (19)
 
where 0≦x/k 2 &lt;CR and 0≦r y &lt;k 2  (property of the remainder).
 
     Also in this case, the limits of the final remainder r are taken into account because in general the following relations apply:
 
 y·k   1   +x =( q   y   ·k   2 )+( r   y   +x )  (20)
 
0 ≦r   y   +x&lt;k   2 ( CR+ 1)  (21)
 
     Also in this embodiment, block  220  hence corrects the partial results. For example, block  220  can determine the quotient q and the remainder r, i.e., the final physical address (q, r), on the basis of the following relations: 
     
       
         
           
             
               
                 
                   
                     
                       
                         y 
                         · 
                         
                           k 
                           1 
                         
                       
                       + 
                       x 
                     
                     = 
                     
                       
                         
                           ( 
                           
                             
                               q 
                               y 
                             
                             + 
                             
                               q 
                               adj 
                             
                           
                           ) 
                         
                         · 
                         
                           k 
                           2 
                         
                       
                       + 
                       r 
                     
                   
                   ⁢ 
                   
                     
 
                   
                   ⁢ 
                   where 
                 
               
               
                 
                   ( 
                   22 
                   ) 
                 
               
             
             
               
                 
                   
                     q 
                     adj 
                   
                   = 
                   
                     { 
                     
                       
                         
                           0 
                         
                         
                           
                             0 
                             ≤ 
                             
                               
                                 r 
                                 y 
                               
                               + 
                               x 
                             
                             &lt; 
                             
                               k 
                               2 
                             
                           
                         
                       
                       
                         
                           1 
                         
                         
                           
                             
                               k 
                               2 
                             
                             ≤ 
                             
                               
                                 r 
                                 y 
                               
                               + 
                               x 
                             
                             &lt; 
                             
                               2 
                               · 
                               
                                 k 
                                 2 
                               
                             
                           
                         
                       
                       
                         
                           ⋮ 
                         
                         
                           ⋮ 
                         
                       
                       
                         
                           CR 
                         
                         
                           
                             
                               CR 
                               · 
                               
                                 k 
                                 2 
                               
                             
                             ≤ 
                             
                               
                                 r 
                                 y 
                               
                               + 
                               x 
                             
                             &lt; 
                             
                               
                                 ( 
                                 
                                   CR 
                                   + 
                                   1 
                                 
                                 ) 
                               
                               · 
                               
                                 k 
                                 2 
                               
                             
                           
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   23 
                   ) 
                 
               
             
             
               
                 
                   r 
                   = 
                   
                     { 
                     
                       
                         
                           
                             
                               r 
                               y 
                             
                             + 
                             x 
                           
                         
                         
                           
                             0 
                             ≤ 
                             
                               
                                 r 
                                 y 
                               
                               + 
                               x 
                             
                             &lt; 
                             
                               k 
                               2 
                             
                           
                         
                       
                       
                         
                           
                             
                               r 
                               y 
                             
                             + 
                             x 
                             - 
                             
                               k 
                               2 
                             
                           
                         
                         
                           
                             
                               k 
                               2 
                             
                             ≤ 
                             
                               
                                 r 
                                 y 
                               
                               + 
                               x 
                             
                             &lt; 
                             
                               2 
                               · 
                               
                                 k 
                                 2 
                               
                             
                           
                         
                       
                       
                         
                           ⋮ 
                         
                         
                           
                               
                           
                         
                       
                       
                         
                           
                             
                               r 
                               y 
                             
                             + 
                             x 
                             - 
                             
                               CR 
                               · 
                               
                                 k 
                                 2 
                               
                             
                           
                         
                         
                           
                             
                               CR 
                               · 
                               
                                 k 
                                 2 
                               
                             
                             ≤ 
                             
                               
                                 r 
                                 y 
                               
                               + 
                               x 
                             
                             &lt; 
                             
                               
                                 ( 
                                 
                                   CR 
                                   + 
                                   1 
                                 
                                 ) 
                               
                               · 
                               
                                 k 
                                 2 
                               
                             
                           
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   24 
                   ) 
                 
               
             
           
         
       
     
       FIG. 7  shows a block diagram of a possible circuit that implements Eqs. (22) to (24). Also in this case, block  200   y  implements Eq. (9), i.e., the translation of the component y into the logical-address space (q y , r y ). 
     In this embodiment, block  200   x  is not envisaged, and block  220  receives the partial result (q y , r y ) and the component x directly to form the final result (q, r). 
     In the embodiment considered, block  220  comprises an adder  2202  for computing the sum (r y +x), and then a check is made to see whether the results need to be corrected, as shown with reference to Eqs. (22) to (24). 
     In the embodiment considered, said check is implemented via a comparator  2206  that verifies whether the sum (r y +x) lies in one of the intervals [0;k 2 [, [k 2 ;2·k 2 [, . . . , [CR·k 2 ; (CR+1)·k 2 [. The result of the check is given to two multiplexers  2208  and  2210 , which yield the respective correction values. In particular, the multiplexer  2208  supplies the respective correction value selected from among “0”, −k 2 , . . . , −CR·k 2  to an adder  2212  for computing the final remainder r, and the multiplexer  2210  supplies the respective correction value selected from among “0”, “1”, . . . , CR to an adder  2214  for computing the final quotient q. 
     This embodiment does hence not require the conversion block  200   x  and the adder  2204 . However, the control circuit, i.e., the comparator  2206  and the multiplexers  2208  and  2210 , are more complex. In fact, this approach usually occupies less area if the parameter CR is less than 5. 
     The circuits described herein hence compute the quotient q and remainder r of the division (y·k 1 +x)/k 2  substantially via three functional blocks. The first circuit, i.e., block  200   y , computes the quotient q y  and the remainder r y  of the function y·k 1 /k 2  via a static-conversion function by exploiting the fact that the parameters k 1  and k 2  are constant. 
     The second circuit computes the remainder r of the division. In particular, this circuit combines the partial remainder r y  with the parameter x, and verifies whether the result of the combination is to be corrected. 
     In the second embodiment ( FIG. 7 ) the adder  2202  combines the partial remainder r y  directly with the parameter x, block  2206  verifies the result of the combination x+r y , and the adder  2212  together with the multiplexer  2208  correct the result. 
     Instead, in the first embodiment ( FIG. 5 ) the combination of the partial remainder r y  with the parameter x is made in two steps, i.e., via block  220   x  and the adder  2202 . This enables reduction both of the part of the checks made via block  2206  and of the part of the correction made via blocks  2208  and  2212 , because block  200   x  guarantees that the result of the combination r x +r y  is always less than 2 k 2 . 
     Finally, the third circuit computes the quotient q of the division. In particular, the third circuit corrects the quotient q y  if the verification made by the second circuit indicates that also the remainder has been corrected. 
     In the second embodiment ( FIG. 7 ), the correction is performed via the adder  2214  and the multiplexer  2210 , which yields the overflow number of the sum x+r y  with respect to the maximum value k 2 . 
     Instead, in the first embodiment ( FIG. 5 ) the correction of the partial quotient q y  is made in two steps, i.e., via the adder  2204  and the adder (incrementer)  2214 . The first adder  2204  corrects the contribution of the component x—i.e., it adds the value of q x  supplied by block  200   x —, whereas the second adder  2214  corrects the possible “overflow” of the sum r x +r y  with respect to the maximum value k 2  supplied by the multiplexer  2210 . 
     The circuits shown in  FIGS. 5 and 7  have been used to carry out a conversion of different logical-address spaces and physical-address spaces, for example from 162×132 to 480×48, from 220×176 to 480×82, and from 320×240 to 480×160. In general, it has been possible to obtain a reduction of occupation of area within the integrated circuit (typically between 50% and 80%) as compared to the solution shown in  FIG. 2 . The circuits described herein are also considerably faster, enabling the use of the conversion modules also in applications with high clock frequency (typically three or four times faster than the solution shown in  FIG. 2 ). 
     The circuit shown in  FIG. 7  typically occupies less area than the circuit shown in  FIG. 5  even though the circuit shown in  FIG. 5  is typically faster. 
     Of course, without prejudice to the principle of the invention, the details of implementation and the embodiments may vary widely with respect to what has been described and illustrated herein purely by way of example, without thereby departing from the scope of the present invention, as defined by the ensuing claims.