Method and apparatus for efficient derivation of modulo arithmetic for frequency selection

• US 7,243,118 B2
• Filed: 07/30/2003
• Issued: 07/10/2007
• Est. Priority Date: 07/30/2003
• Status: Expired due to Fees

• Current Assignee: Avago Technologies General IP PTE Limited (Broadcom, Inc.)
• Original Assignee: Broadcom Corporation (Broadcom, Inc.)
• Inventors: Lou, Wenkwei
• Primary Examiner(s): MALZAHN, DAVID H
• Application Number:
  US10/630,122
• Publication Number:
  US 20050027776A1
• Time in Patent Office: 1,441 Days
• Field of Search: 708/491
• US Class Current: 708/491
• CPC Class Codes: G06F 7/72 using residue arithmetic

Abstract

A method and apparatus for efficiently deriving modulo arithmetic solutions for frequency selection in transceivers. A frequency for communication between a wireless user interface device and a wirelessly enabled host is generated by calculating a modulo solution for an input variable. In some embodiments of the invention, the communication between the user input device and the wirelessly enabled host complies with the Bluetooth wireless communication standard. For the embodiments of the present invention relating to communications systems implementing the Bluetooth standard, a method and apparatus is disclosed for generating communication frequencies based on modulo 23 and modulo 79 solutions input variables. The method and apparatus of the present invention can generate the communication frequency with a minimum number of calculations using simple binary addition, as opposed to prior art methods that generally require numerous iterations and complex calculations.

Claims

1. A method of generating a communication frequency based on a modulo 23 solution for an input variable, comprising:

receiving an input variable;

generating an intermediate modulo 23 solution by;

generating a binary representation of said input variable;

using the five rightmost digits of said binary representation of said input variable to represent a first intermediate remainder (R′

);

using the remaining three leftmost digits to represent a first intermediate quotient (Q′

);

expressing said first intermediate modulo solution as a sum of said first intermediate quotient (Q′

) multiplied by 9 plus said first intermediate remainder (R′

); and

comparing said first intermediate modulo solution to the quantity 32;

indicating said first intermediate modulo solution as the modulo remainder (R) if said quantity of said first intermediate modulo solution is less than 23; and

using said modulo remainder to generate said communication frequency.

2. The method according to claim 1 wherein an iterative process is performed if said first intermediate modulo solution is greater than 32, said iterative process comprising:

(a) generating a binary representation of said first intermediate modulo solution;

(b) using the five rightmost digits of said binary representation of said first intermediate modulo solution to represent a second intermediate remainder (R″

)

(c) using said remaining three leftmost digits to represent a second intermediate quotient (Q″

);

(d) expressing said second intermediate modulo solution as a sum of said second intermediate quotient (Q″

) multiplied by 9 plus said second intermediate remainder (R″

);

(e) comparing said second intermediate modulo solution to the quantity 32;

(f) indicating said second intermediate modulo solution as the modulo remainder (R) if said quantity of said second intermediate modulo solution is less than 23; and

(g) repeating steps (a) through (f) if said intermediate modulo solution is greater than 32.

3. The method according to claim 2, wherein said multiplication of said second intermediate quotient (Q″

) by 9 is accomplished by;

shifting said binary representation of Q″

to the left by three places; and

adding said left-shifted value of Q″

to the original value of Q″

.

4. The method according to claim 1, wherein said multiplication of said first intermediate quotient (Q′

) by 9 is accomplished by;

shifting said binary representation of Q′

to the left by three places; and

adding said left-shifted value of Q′

to the original value of Q′

.

5. A method of generating a modulo 79 solution for an input variable, comprising:

receiving an input variable;

generating an intermediate modulo 79 solution by;

generating a binary representation of said input variable;

using the seven rightmost digits of said binary representation of said input variable to represent a first intermediate remainder (R′

);

using the remaining leftmost digits to represent a first intermediate quotient (Q′

);

expressing said first intermediate modulo solution as a sum of said first intermediate quotient (Q′

) multiplied by 49 plus said first intermediate remainder (R′

); and

comparing said first intermediate modulo solution to the quantity 128;

indicating said first intermediate modulo solution as the modulo remainder (R) if said quantity of said first intermediate modulo solution is less than 79; and

using said modulo remainder to generate said communication frequency.

6. The method according to claim 5 wherein an iterative process is performed if said first intermediate modulo solution is greater than 128, said iterative process comprising:

(a) generating a binary representation of said first intermediate modulo solution;

(b) using the seven rightmost digits of said binary representation of said first intermediate modulo solution to represent a second intermediate remainder (R″

)

(c) using said remaining leftmost digits to represent a second intermediate quotient (Q″

);

(d) expressing said second intermediate modulo solution as a sum of said second intermediate quotient (Q″

) multiplied by 49 plus said second intermediate remainder (R″

);

(e) comparing said second intermediate modulo solution to the quantity 128;

(f) indicating said second intermediate modulo solution as the modulo remainder (R) if said quantity of said second intermediate modulo solution is less than 79; and

(g) repeating steps (a) through (f) if said intermediate modulo solution is greater than 128.

7. The method according to claim 6, wherein said multiplication of said second intermediate quotient (Q″

) by 49 is accomplished by;

shifting said binary representation of Q″

to the left by 5 places to define a first shifted Q″

value,

shifting said binary representation of Q″

to the left by 4 places to define a second shifted Q″

value; and

adding said first and second shifted values of Q″

to the original value of Q″

.

8. The method according to claim 5, wherein said multiplication of said first intermediate quotient (Q′

) by 49 is accomplished by;

shifting said binary representation of Q′

to the left by 5 places to define a first shifted Q′

value,

shifting said binary representation of Q′

to the left by 4 places to define a second shifted Q′

value; and

adding said first and second shifted values of Q′

to the original value of Q′

.

9. A system for generating a communication signal at a predetermined frequency, comprising:

a transceiver, said transceiver comprising;

a radio frequency module;

a baseband core further comprising a frequency control functionality;

a frequency hopper within said baseband core of said transceiver, said frequency hopper being operable to generate a plurality of frequencies related to a modulo 23 solution of an input variable, wherein said frequency hopper generates an intermediate modulo 23 solution by;

generating a binary representation of said input variable;

using the five rightmost digits of said binary representation of said input variable to represent a first intermediate remainder (R′

);

using the remaining three leftmost digits to represent a first intermediate quotient (Q′

);

expressing said first intermediate modulo solution as a sum of said first intermediate quotient (Q′

) multiplied by 9 plus said first intermediate remainder (R′

);

comparing said first intermediate modulo solution to the quantity 32; and

indicating said first intermediate modulo solution as the modulo remainder (R) if said quantity of said first intermediate modulo solution is less than 23.

10. The system according to claim 9 wherein an iterative process is performed if said first intermediate modulo solution is greater than 32, said iterative process comprising:

(a) generating a binary representation of said first intermediate modulo solution;

(b) using the five rightmost digits of said binary representation of said first intermediate modulo solution to represent a second intermediate remainder (R″

)

(c) using said remaining three leftmost digits to represent a second intermediate quotient (Q″

);

(d) expressing said second intermediate modulo solution as a sum of said second intermediate quotient (Q″

) multiplied by 9 plus said second intermediate remainder (R″

);

(e) comparing said second intermediate modulo solution to the quantity 32;

(f) indicating said second intermediate modulo solution as the modulo remainder (R) if said quantity of said second intermediate modulo solution is less than 23; and

(g) repeating steps (a) through (f) if said intermediate modulo solution is greater than 32.

11. The system according to claim 10, wherein said multiplication of said second intermediate quotient (Q″

) by 9 is accomplished by;

shifting said binary representation of Q″

to the left by three places; and

adding said left-shifted value of Q″

to the original value of Q″

.

12. The system according to claim 9, wherein said multiplication of said first intermediate quotient (Q′

) by 9 is accomplished by;

shifting said binary representation of Q′

to the left by three places; and

adding said left-shifted value of Q′

to the original value of Q′

.

13. A system for generating a communication signal at a predetermined frequency, comprising:

a transceiver, said transceiver comprising;

a radio frequency module;

a baseband core further comprising a frequency control functionality;

a frequency hopper within said baseband core of said transceiver, said frequency hopper being operable to generate a plurality of frequencies related to a modulo 79 solution of an input variable, wherein said frequency hopper generates an intermediate modulo 79 solution by;

generating a binary representation of said input variable;

using the seven rightmost digits of said binary representation of said input variable to represent a first intermediate remainder (R′

);

using the remaining leftmost digits to represent a first intermediate quotient (Q′

);

expressing said first intermediate modulo solution as a sum of said first intermediate quotient (Q′

) multiplied by 49 plus said first intermediate remainder (R′

);

comparing said first intermediate modulo solution to the quantity 128; and

indicating said first intermediate modulo solution as the modulo remainder (R) if said quantity of said first intermediate modulo solution is less than 79.

14. The system according to claim 13 wherein an iterative process is performed if said first intermediate modulo solution is greater than 128, said iterative process comprising:

(a) generating a binary representation of said first intermediate modulo solution;

(b) using the seven rightmost digits of said binary representation of said first intermediate modulo solution to represent a second intermediate remainder (R″

)

(c) using said remaining leftmost digits to represent a second intermediate quotient (Q″

);

(d) expressing said second intermediate modulo solution as a sum of said second intermediate quotient (Q″

) multiplied by 49 plus said second intermediate remainder (R″

);

(e) comparing said second intermediate modulo solution to the quantity 128;

(f) indicating said second intermediate modulo solution as the modulo remainder (R) if said quantity of said second intermediate modulo solution is less than 79; and

(g) repeating steps (a) through (f) if said intermediate modulo solution is greater than 128.

15. The system according to claim 14, wherein said multiplication of said second intermediate quotient (Q″

) by 9 is accomplished by;

shifting said binary representation of Q′

to the left by 5 places to define a first shifted Q′

value,

shifting said binary representation of Q′

to the left by 4 places to define a second shifted Q′

value; and

adding said first and second shifted values of Q′

to the original value of Q′

.

16. The system according to claim 13, wherein said multiplication of said first intermediate quotient (Q′

) by 49 is accomplished by;

shifting said binary representation of Q′

to the left by 5 places to define a first shifted Q′

value,

shifting said binary representation of Q′

to the left by 4 places to define a second shifted Q′

value; and

adding said first and second shifted values of Q′

to the original value of Q′

.

17. A system for generating communication frequencies in a wireless interface system that services communications between a wirelessly enabled host and at least one user input device, comprising:

a wireless interface unit that wirelessly interfaces with the wirelessly enabled host, wherein the wireless interface unit comprises;

an analog module including a transceiver unit and a frequency synthesizer,

a baseband module including a frequency hopper, wherein said frequency hopper is operable to generate a plurality of frequencies related to a modulo 23 solution of an input variable, wherein said frequency hopper generates an intermediate modulo 23 solution by;

generating a binary representation of said input variable;

using the five rightmost digits of said binary representation of said input variable to represent a first intermediate remainder (R′

);

using the remaining three leftmost digits to represent a first intermediate quotient (Q′

);

expressing said first intermediate modulo solution as a sum of said first intermediate quotient (Q′

) multiplied by 9 plus said first intermediate remainder (R′

);

comparing said first intermediate modulo solution to the quantity 32; and

indicating said first intermediate modulo solution as the modulo remainder (R) if said quantity of said first intermediate modulo solution is less than 23; and

wherein said frequency synthesizer is operable to generate a frequency hop sequence using said result of said modulo 23 solution generated by said frequency hopper.

18. The system according to claim 17 wherein an iterative process is performed if said first intermediate modulo solution is greater than 32, said iterative process comprising:

(a) generating a binary representation of said first intermediate modulo solution;

(b) using the five rightmost digits of said binary representation of said first intermediate modulo solution to represent a second intermediate remainder (R″

)

(c) using said remaining three leftmost digits to represent a second intermediate quotient (Q″

);

(d) expressing said second intermediate modulo solution as a sum of said second intermediate quotient (Q″

) multiplied by 9 plus said second intermediate remainder (R″

);

(e) comparing said second intermediate modulo solution to the quantity 32;

(f) indicating said second intermediate modulo solution as the modulo remainder (R) if said quantity of said second intermediate modulo solution is less than 23; and

(g) repeating steps (a) through (f) if said intermediate modulo solution is greater than 32.

19. The system according to claim 18, wherein said multiplication of said second intermediate quotient (Q″

) by 9 is accomplished by;

shifting said binary representation of Q″

to the left by three places; and

adding said left-shifted value of Q″

to the original value of Q″

.

20. The system according to claim 17, wherein said multiplication of said first intermediate quotient (Q′

) by 9 is accomplished by;

shifting said binary representation of Q′

to the left by three places; and

adding said left-shifted value of Q′

to the original value of Q′

.

21. A system for generating communication frequencies in a wireless interface system that services communications between a wirelessly enabled host and at least one user input device, comprising:

a wireless interface unit that wirelessly interfaces with the wirelessly enabled host, wherein the wireless interface unit comprises;

an analog module including a transceiver unit and a frequency synthesizer,

a baseband module including a frequency hopper, wherein said frequency hopper is operable to generate a plurality of frequencies related to a modulo 79 solution of an input variable, wherein said frequency hopper generates an intermediate modulo 79 solution by;

generating a binary representation of said input variable;

using the seven rightmost digits of said binary representation of said input variable to represent a first intermediate remainder (R′

);

using the remaining leftmost digits to represent a first intermediate quotient (Q′

);

expressing said first intermediate modulo solution as a sum of said first intermediate quotient (Q′

) multiplied by 49 plus said first intermediate remainder (R′

);

comparing said first intermediate modulo solution to the quantity 128; and

indicating said first intermediate modulo solution as the modulo remainder (R) if said quantity of said first intermediate modulo solution is less than 79.

22. The system according to claim 21 wherein an iterative process is performed if said first intermediate modulo solution is greater than 128, said iterative process comprising:

(a) generating a binary representation of said first intermediate modulo solution;

(b) using the seven rightmost digits of said binary representation of said first intermediate modulo solution to represent a second intermediate remainder (R″

)

(c) using said remaining leftmost digits to represent a second intermediate quotient (Q″

);

(d) expressing said second intermediate modulo solution as a sum of said second intermediate quotient (Q″

) multiplied by 49 plus said second intermediate remainder (R″

);

(e) comparing said second intermediate modulo solution to the quantity 128;

(f) indicating said second intermediate modulo solution as the modulo remainder (R) if said quantity of said second intermediate modulo solution is less than 79; and

(g) repeating steps (a) through (f) if said intermediate modulo solution is greater than 128.

23. The system according to claim 22, wherein said multiplication of said first intermediate quotient (Q′

) by 49 is accomplished by;

shifting said binary representation of Q′

to the left by 5 places to define a first shifted Q′

value,

shifting said binary representation of Q′

to the left by 4 places to define a second shifted Q′

value; and

adding said first and second shifted values of Q′

to the original value of Q′

.

24. The system according to claim 23, wherein said multiplication of said second intermediate quotient (Q″

) by 9 is accomplished by;

shifting said binary representation of Q′

to the left by 5 places to define a first shifted Q′

value,

shifting said binary representation of Q′

to the left by 4 places to define a second shifted Q′

value; and

adding said first and second shifted values of Q′

to the original value of Q′

.