Calculation of trigonometric functions in an integrated circuit device

• US 8,510,354 B1
• Filed: 03/12/2010
• Issued: 08/13/2013
• Est. Priority Date: 03/12/2010
• Status: Active Grant

• Current Assignee: Altera Corporation (Intel Corporation)
• Original Assignee: Altera Corporation (Intel Corporation)
• Inventors: Langhammer, Martin
• Primary Examiner(s): Yaary, Michael D
• Application Number:
  US12/722,683
• Time in Patent Office: 1,250 Days
• Field of Search: None
• US Class Current: 708/200
• CPC Class Codes: G06F 7/548 Trigonometric functions; Co-ordinate transformations

Abstract

Circuitry for computing on x and y datapaths a trigonometric function of an input on a z datapath includes a comparison element to determine that the input is at or above a threshold, or below the threshold. The circuitry also includes a first left-shifter for shifting the z datapath by a constant when the input is below the threshold, and a second left-shifter for shifting an initialization value of the x datapath when the input is below the threshold. The circuitry further includes a look-up table including inverse tangent values based on negative powers of 2, and based on negative powers of 2-plus-the-constant and shifted by the constant, for adding to/subtracting from the z datapath, shifters for right-shifting elements of the x and y datapaths by amounts incorporating the constant and respective predetermined shift amounts that are adjusted when the input is below the threshold.

Claims

1. Circuitry for computing on x and y datapaths a trigonometric function of an input on a z datapath, said circuitry comprising:

a comparison element to determine that said input is at or above a threshold, or below said threshold;

a first left-shifter for shifting said z datapath by a constant when said input is below said threshold;

a second left-shifter for shifting an initialization value of said x datapath when said input is below said threshold;

a look-up table including inverse tangent values based on negative powers of 2, and based on negative powers of 2-plus-said-constant and shifted by said constant, for adding to/subtracting from said z datapath; and

shifters for right-shifting elements of said x and y datapaths by amounts incorporating said constant and respective predetermined shift amounts that are adjusted when said input is below said threshold.

2. The circuitry of claim 1 wherein said computing implements CORDIC.

3. The circuitry of claim 1 wherein said constant is 0 when said input is at or above said threshold and is a predetermined value when said input is below said threshold.

4. The circuitry of claim 1 wherein:

said comparison element is a count-leading-zeroes module; and

said constant is 0 when said input is at or above said threshold and is a value based on a leading-zeroes count from said count-leading-zeroes module when said input is below said threshold.

5. The circuitry of claim 4 wherein said second left-shifter left-shifts said input of said x datapath by said constant.

6. The circuitry of claim 1 wherein:

said comparison element is a count-leading-ones module; and

said constant is 0 when said input is at or above said threshold and is a value based on a leading-ones count from said count-leading-ones module when said input is below said threshold.

7. The circuitry of claim 6 wherein said second left-shifter left-shifts said input of said x datapath by said constant.

8. The circuitry of claim 1 wherein said x datapath is scaled by an infinite series and said series is adjusted by a number of series terms where said number is based on said constant.

9. The circuitry of claim 1 wherein when said input is below said threshold, at least one of said predetermined shift amounts is adjusted by a predetermined value.

10. The circuitry of claim 1 wherein, when said input is below said threshold:

said initialization value of said x datapath is saturated; and

contribution of most significant bits of said x datapath to said y datapath is reconstructed prior to said shifters for right-shifting.

11. The circuitry of claim 10 wherein when said input is below said threshold, at least one of said predetermined shift amounts is adjusted based on a leading-zeroes count of said input.

12. The circuitry of claim 11 wherein, prior to being shifted by said predetermined shift amount adjusted based on said leading-zeroes count of said input, a number of most significant bits of elements of said x datapath are zeroed, said number of most significant bits being based on said leading-zeroes count of said input.

13. The circuitry of claim 12 wherein an entry value of said x datapath is left-shifted based on said leading zeroes count of said input.

14. The circuitry of claim 10 wherein when said input is below said threshold, at least one of said predetermined shift amounts is adjusted based on a leading-ones count of said input.

15. The circuitry of claim 14 wherein, prior to being shifted by said predetermined shift amount adjusted based on said leading-ones count of said input, a number of most significant bits of elements of said x datapath are changed to ones, said number of most significant bits being based on said leading-ones count of said input.

16. The circuitry of claim 14 wherein an entry value of said x datapath is left-shifted based on said leading ones count of said input.

17. A method of configuring a programmable integrated circuit device as circuitry for computing on x and y datapaths a trigonometric function of an input on a z datapath, said method comprising:

configuring logic of said programmable integrated circuit device as a comparison element to determine that said input is at or above a threshold, or below said threshold;

configuring logic of said programmable integrated circuit device as a first left-shifter for shifting said z datapath by a constant when said input is below said threshold;

configuring logic of said programmable integrated circuit device as a second left-shifter for shifting an initialization value of said x datapath when said input is below said threshold;

configuring memory of said programmable integrated circuit device as a look-up table including inverse tangent values based on negative powers of 2, and based on negative powers of 2-plus-said-constant and shifted by said constant, for adding to/subtracting from said z datapath; and

configuring logic of said programmable integrated circuit device as shifters for right-shifting elements of said x and y datapaths by amounts incorporating said constant and respective predetermined shift amounts that are adjusted when said input is below said threshold.

18. The method of claim 17 wherein said programmable integrated circuit device is configured to implement CORDIC.

19. The method of claim 17 wherein said constant is 0 when said input is at or above said threshold and is a predetermined value when said input is below said threshold.

20. The method of claim 17 wherein:

said configuring logic of said programmable integrated circuit device as a comparison element comprises configuring logic of said programmable integrated circuit device as a count-leading-zeroes module; and

said constant is 0 when said input is at or above said threshold and is a value based on a leading-zeroes count from said count-leading-zeroes module when said input is below said threshold.

21. The method of claim 20 wherein said configuring logic of said programmable integrated circuit device as a second left-shifter comprises configuring said logic to left-shift said input of said x datapath by said constant.

22. The method of claim 17 wherein:

said configuring logic of said programmable integrated circuit device as comparison element comprises configuring logic of said programmable integrated circuit device as a count-leading-ones module; and

said constant is 0 when said input is at or above said threshold and is a value based on a leading-ones count from said count-leading-ones module when said input is below said threshold.

23. The method of claim 22 wherein said configuring logic of said programmable integrated circuit device as a second left-shifter comprises configuring logic of said programmable integrated circuit device to left-shift said input of said x datapath by said constant.

24. The method of claim 17 comprising configuring logic of said programmable integrated circuit device to scale said x datapath by an infinite series and to adjust said series by a number of series terms where said number is based on said constant.

25. The method of claim 17 comprising configuring logic of said programmable integrated circuit device so that when said input is below said threshold, at least one of said predetermined shift amounts is adjusted by a predetermined value.

26. The method of claim 17 comprising configuring logic of said programmable integrated circuit device so that, when said input is below said threshold:

said initialization value of said x datapath is saturated; and

contribution of most significant bits of said x datapath to said y datapath is reconstructed prior to said shifters for right-shifting.

27. The method of claim 26 comprising configuring logic of said programmable integrated circuit device so that when said input is below said threshold, at least one of said predetermined shift amounts is adjusted based on a leading-zeroes count of said input.

28. The method of claim 27 comprising configuring logic of said programmable integrated circuit device so that, prior to being shifted by said predetermined shift amount adjusted based on said leading-zeroes count of said input, a number of most significant bits of elements of said x datapath are zeroed, said number of most significant bits being based on said leading-zeroes count of said input.

29. The method of claim 28 comprising configuring logic of said programmable integrated circuit device to left-shift an entry value of said x datapath based on said leading zeroes count of said input.

30. The method of claim 26 comprising configuring logic of said programmable integrated circuit device so that when said input is below said threshold, at least one of said predetermined shift amounts is adjusted based on a leading-ones count of said input.

31. The method of claim 30 comprising configuring logic of said programmable integrated circuit device so that, prior to being shifted by said predetermined shift amount adjusted based on said leading-ones count of said input, a number of most significant bits of elements of said x datapath are changed to ones, said number of most significant bits being based on said leading-ones count of said input.

32. The method of claim 30 comprising configuring logic of said programmable integrated circuit device so that an entry value of said x datapath is left-shifted based on said leading ones count of said input.

33. A non-transitory machine-readable data storage medium encoded with machine-executable instructions for configuring a programmable integrated circuit device as circuitry for computing on x and y datapaths a trigonometric function of an input on a z datapath, said instructions comprising:

instructions to configure logic of said programmable integrated circuit device as a comparison element to determine that said input is at or above a threshold, or below said threshold;

instructions to configure logic of said programmable integrated circuit device as a first left-shifter for shifting said z datapath by a constant when said input is below said threshold;

instructions to configure logic of said programmable integrated circuit device as a second left-shifter for shifting an initialization value of said x datapath when said input is below said threshold;

instructions to configure memory of said programmable integrated circuit device as a look-up table including inverse tangent values based on negative powers of 2, and based on negative powers of 2-plus-said-constant and shifted by said constant, for adding to/subtracting from said z datapath; and

instructions to configure logic of said programmable integrated circuit device as shifters for right-shifting elements of said x and y datapaths by amounts incorporating said constant and respective predetermined shift amounts that are adjusted when said input is below said threshold.

34. The non-transitory machine-readable data storage medium of claim 33 comprising instructions to configure logic of said programmable integrated circuit device so that, when said input is below said threshold:

said initialization value of said x datapath is saturated; and

contribution of most significant bits of said x datapath to said y datapath is reconstructed prior to said shifters for right-shifting.

35. The non-transitory machine-readable data storage medium of claim 34 comprising instructions to configure logic of said programmable integrated circuit device so that when said input is below said threshold, at least one of said predetermined shift amounts is adjusted based on a leading-zeroes count of said input.

36. The non-transitory machine-readable data storage medium of claim 35 comprising instructions to configure logic of said programmable integrated circuit device so that, prior to being shifted by said predetermined shift amount adjusted based on said leading-zeroes count of said input, a number of most significant bits of elements of said x datapath are zeroed, said number of most significant bits being based on said leading-zeroes count of said input.

37. The non-transitory machine-readable data storage medium of claim 36 comprising instructions to configure logic of said programmable integrated circuit device to left-shift an entry value of said x datapath based on said leading zeroes count of said input.

38. The non-transitory machine-readable data storage medium of claim 34 comprising instructions to configure logic of said programmable integrated circuit device so that when said input is below said threshold, at least one of said predetermined shift amounts is adjusted based on a leading-ones count of said input.

39. The non-transitory machine-readable data storage medium of claim 38 comprising instructions to configure logic of said programmable integrated circuit device so that, prior to being shifted by said predetermined shift amount adjusted based on said leading-ones count of said input, a number of most significant bits of elements of said x datapath are changed to ones, said number of most significant bits being based on said leading-ones count of said input.

40. The non-transitory machine-readable data storage medium of claim 38 comprising instructions to configure logic of said programmable integrated circuit device so that an entry value of said x datapath is left-shifted based on said leading ones count of said input.