The Gray area of n-ary codes
Pyth, 20 bytes

Msme.H%dGu+G-HsGjHGY


This defines a function g which takes two integers as parameters. Take a look at this online demonstration: Pyth Compiler/Executor. 

Explanation:

Msme.H%dGu+G-HsGjHGY  
M                     def g(G, H): return _
                jHG      convert H to base G
         u      jHGY     reduce(lambda G, H: _, jHG, [])
          +G-HsG            G + [H - sum(G)]
  m                      map each number d to:
   e.H%dG                   hex-representation(d % G)[-1]
 s                       sum (join all digits)


This code is a little bit confusing. There are 4 function parameters in this code: two of them are called G and two of them are called H. The G in +G-HsG is different from the G in jHG or %dG.