How to compute the free distance in TCM (Trellis-Coded Modulation)?
The free distance of a Trellis Coded Modulation system implemented either on BPSK or QPSK is a straightforward calculation. You'd have to compute the free distance $d_{free}$ of the convolutional code which is known as the Minimum Squared Euclidean Distance (MSED). Now, if the code has set-partitioned labeling to achieve coding gains over conventional labeling, then the minimum distance is given as $$\text{min}(d_{free},d_{ic})$$
where $d_{ic}$ is the minimum squared Intra-coset distance which can be calculated from the mapping. Having said this, the MSED of the convolutional code can be computed the same way its $d_f$ (the hamming free distance) is computed. You need to do a trellis search and replace hamming weights with squared euclidean minimum distances with the all zero-sequence mapping (this is valid because any convolutional code is linear and if the mapping is BPSK or QPSK, every symbol has a decoding Voronoi region that has the same area and the same shape as every other sequence). I believe you've implemented your trellis search perfectly. Having said this, the Ungerboeck code cannot be performing better than a code which has a higher Euclidean $d_{min}$. Suggestions:  1. Either you're computing one of the distances wrongly2. Are you sure about the minimum distance of the Ungerboeck code?