Reduced-modulus address generation using sign-extension and correction

A mixed-modulo adder for adding together a first reduced-width address component having a reduced width and a second reduced-width address component in a reduced modulus, while further adding in a full-width address component in a full modulus having a full width, the second reduced-width address component having a sign bit indicating if the second reduced-width address component is treated as a positive or a negative number, the mixed-modulo adder comprising:

• sign-extend means, receiving the second reduced-width address component, for extending the second reduced-width address component to the full width by copying the sign bit to a plurality of upper bit-positions in the full width, the plurality of upper bit-positions being bit-positions not present in the reduced width, the sign-extend means outputting an extended address component having the full width;
• a multi-port adder, receiving as inputs the first reduced-width address component after being zero-extended, the extended address component, and the full-width address component, the multi-port adder calculating a full-modulus sum of the inputs received;
• recirculating means, receiving the full-modulus sum from the multi-port adder, for returning the full-modulus sum to one of the inputs of the multi-port adder for use in a subsequent calculation step;
• reduced-modulus carry generator, receiving the first reduced-width address component and the second reduced-width address component, the reduced-modulus carry generator producing a reduced-modulus carry-out if a sum of the first reduced-width address component and the second reduced-width address component is equal to or exceeds the reduced modulus when the second reduced-width address component is treated as positive number;
• and
• correction term input means, responsive to the reduced-modulus carry-out and the sign bit, for inputting a correction term to the multi-port adder during a subsequent step, the correction term being added to the full-modulus sum from the recirulating means, the correction term being an adjustment to the full-modulus sum to compensate for the effect of sign extension and addition of the reduced-modulus address components;
• whereby full-modulus addition is performed on reduced-width address components by sign-extension and addition of the correction term during the subsequent step when signaled by the reduced-modulus carry-out and the sign bit.

A computer-implemented method for adding a first and a second address component to a third address component in a full-width adder on a central processing Unit (CPU), the first and second address components having a reduced width, the third address component having a full width, the first, second, and third address components each being represented by a plurality of signals on a bus, the second address component having a sign bit signal, the method comprising:

• sign-extending the second address component by copying the sign bit signal to additional bit-positions in the full width but not in the reduced width, producing a sign-extended second address component on a full-width bus;
• generating in the full-width adder on the central processing unit the full-width sum of (a) the first address component after being zero-extended, (b) the sign-extended second address component, and (c) the third address component in a full-width adder;
• outputting the full-width sum generated by the full-width adder onto a full-width bus on the central processing unit;
• determining in a reduced-modulus carry generator means on the central processing unit if a partial sum of the first address component and the second address component is equal to or exceeds a reduced modulus;
• generating a reduced-modulus carry-out signal if the partial sum is equal to or exceeds the reduced modulus;
• and
• adding a correction term to the full-width sum if the sign bit signal indicates a positive value and the reduced-modulus carry-out signal is generated, or if the sign bit signal indicates a negative value and the reduced-modulus carry-out signal is not generated.

A mixed-modulo adder for adding together a subset of inputs in a reduced modulus, while further adding to the subset of inputs a full-width binary number in a full modulus, the mixed-modulo adder comprising:

• a multi-port adder, receiving as inputs the subset of inputs in a reduced modulus and the full-width binary number, the multi-port adder calculating the full-modulus sum of the subset of inputs after being extended and the full-width binary number;
• recirculating means, receiving the full-modulus sum from the multi-port adder, for returning the full-modulus sum to one of the inputs of the multi-port adder for use in a possible subsequent calculation step;
• reduced-modulus carry generator, receiving the subset of inputs in a reduced modulus, the reduced-modulus carry generator producing a reduced-modulus carry-out if a sum of the subset of inputs in a reduced modulus is equal to or exceeds the reduced modulus;
• and
• correction term input means, responsive to the reduced-modulus carry-out, for inputting a correction term to the multi-port adder during the possible subsequent calculation step, the possible subsequent calculation step occurring if the reduced-modulus carry-out is signaled but the possible subsequent calculation step not occurring if the reduced-modulus carry-out is not signaled, the correction term being added to the full-modulus sum from the recirculating means in the possible subsequent calculation step, the correction term for being an adjustment to the full-modulus sum to compensate for the effect of addition of the subset of inputs in a reduced modulus;
• whereby full-modulus addition is performed on a subset of inputs by addition of the correction term during the possible subsequent calculation step when signaled by the reduced-modulus carry-out.