Techniques to improve the performance of a Turbo decoder when scale information for the bits in a code segment to be decoded is not known. A number of hypotheses are formed for the code segment, witheach hypothesis corresponding to a particular set of one or more values for a set of one or more parameters used for decoding the code segment. For the MAP decoding scheme, these parameters may be forthe sequence of scaling factors used to scale the bits prior to decoding and/or a scale used to evaluate a (e.g., min*) function for the MAP decoding. The code segment is decoded based on the MAP decoding scheme and in accordance with each hypothesis. The quality of the decoded result for each hypothesis is determined based on one or more performance metrics. The decoded bits for the best hypothesis are provided as the Turbo decoder output.