Algorithms – How to Decode FLAC to PCM

algorithmsccompression

I'm trying to program a very basic FLAC player using 100% C# completely from scratch. My understanding of this type of thing is very limited, so I'm using this project as a way to learn about compression and decompression. I'm a computer science and math major currently in university, so I'm not adverse to learning whatever math may be involved.

I've looked up the format specifications on xiph.org and I understand how the headers and all are structured, but I can't seem to find a concise explanation of how the audio compression works. How do I go about converting the frames to pcm?

Sadly, my knowledge of C/C++ is extremely limited, as I only have experience with Java and C#. As such, trying to navigate the c++ code already out there is not a great starting point. I looked at FlacBox and learned quite a bit from it, but it's barely commented at all and I am lost trying to figure out how the conversion from flac to pcm works.

So what should I read as far as math goes so I can get started with this? Where can I find a basic algorithm for converting the audio frames to wav? Thanks.

Best Answer

You need to look a little closer at the format page on the FLAC website. The "prediction" paragraph leads to this article, which describes the AudioPak algorithm in detail, and also Shorten.

You should learn and understand these algorithms and the associated math before digging into the source code. That might take awhile.

Related Solutions

Find an algorithm for creating 3D anaglyphs using a depth map image

This paper might be helpful. It focuses on outdoor/landscapes scenes. The following is an excerpt from the paper's abstract:

This paper presents a new unsupervised technique aimed to generate stereoscopic views estimating depth information from a single input image. Using a single input image, vanishing points/lines are extracted using a few heuristics to generate an approximated depth map. The depth map is then used to generate stereo pairs.

Algorithms – How to Convert a Bounded Knapsack Problem to 0/1 Knapsack Problem

It might be some mistake in your code. I wrote the DP program as mentioned by Naryshkin. For the target span 13, it reports 6+7, and for 15, it reports 2+6+7.

# weight: cable length
# total weight: target span
# value: 1 for each cable
# want minimum number of cables, i.e. minimum total value

def knapsack_01_exact_min(weights, values, W):
    # 0-1 knapsack, exact total weight W, minimizing total value
    n = len(weights)
    values = [0] + values
    weights = [0] + weights
    K = [[0 for i in range(W+1)] for j in range(n+1)]
    choice = [[0 for i in range(W+1)] for j in range(n+1)]
    for i in range(1, n+1):
        for w in range(1, W+1):
            K[i][w] = K[i-1][w]
            choice[i][w] = '|'
            if w >= weights[i]:
                t = K[i-1][w-weights[i]]
                if (w==weights[i] or t) and (K[i][w]==0 or t+values[i] < K[i][w]):
                    choice[i][w] = '\\'
                    K[i][w] = t+values[i]
    return K[n][W], choice

def print_choice(choice, weights):
    i = len(choice)-1
    j = len(choice[0])-1
    weights = [0] + weights
    while i > 0 and j > 0:
        if choice[i][j]=='\\':
            print weights[i],
            j -= weights[i]
        i -= 1
    print

lens = [10, 7, 6] + 5*[3] + 6*[2] + 7*[1]
values = (3+5+6+7)*[1]
span = 13
v, choice = knapsack_01_exact_min(lens, values, span)
print "need %d cables to span %d:" % (v,span),
print_choice(choice, lens)

span = 15
v, choice = knapsack_01_exact_min(lens, values, span)
print "need %d cables to span %d:" % (v,span),
print_choice(choice, lens)

If you adjust the order of the input lengths, it can give other optimal solutions. For example, lens = 5*[3] + 6*[2] + 7*[1] + [10, 7, 6] will give 15=10+2+3.

Related Topic