In other words...

'Paraphrase' in musical terms is analogous to the usual definition of the word as it relates to language, where it means "a restatement of a text or passage giving the meaning in another form; rewording". In music, an original melody (or part of that melody) is used in a new piece and while the essence ('the meaning') of the melody remains its actual notes are changed, whether by the addition of new notes or the subtraction of some of the old notes or just by altering certain of the notes or the melody's rhythm or shape.

Tomás Luis de Victoria's lovely setting of the Ave Maria for four voices paraphrases an old Gregorian plainchant melody. The cantus (soprano) line of Victoria's piece begins with the 'Ave Maria' phrase from from the old chant, unadorned and unaccompanied and continues 'verbatim' with the phrase 'Gratia plena'. Victoria then adds a repeat of that phrase, albeit lowering both of the final two notes by a third. He alters one note of 'Dominus tecum', which he then transposes down a third and repeats. Gradually, the variation of the melody in the soprano line grows freer with an increasing number of changes to the shape of the original plainchant melody as the setting of 'Benedicta tu in mulieribus, et benedictus fructus ventris tui Jesus Christ' proceeds, culminating in a remarkable expansion of the very short original setting of 'Jesus Christ'. The phrases begin at 'Sancta Maria' have only the general arcs of the original. 

What are the other three voices doing? Well, supplying counterpoint for starters, this being Renaissance polyphony. The first 'Gratia pleni' phrase is echoed in turn by the tenor and bass while the alto repeats it but changes the final note. This imitative writing is not usual for the period but, as it isn't a Baroque fugue, the imitation is not particularly strict, nor is it pervasive. The section beginning at 'Sancta Maria', however, switches to homophony and a simple, triple-time rhythm before the metre changes back to duple time at 'peccatoribus' for a final polyphonic flourish. 

There is a second setting of the Ave Maria by Victoria, this time for eight voices - here a double choir. It is even more beautiful. Where the piece we've already met is quite simple and intimate, this setting is public music meant for grand occasions. The upper voice of the first chorus sings the memorable opening phrase, whose opening notes are those of the old Gregorian chant but which then continues along its own path. The upper voice of the second chorus echoes it. The chant is again paraphrased in this piece, though far more elusively. It does becomes very close to the original at 'Benedicta tu in mulieribus'. As often in works for double choir, the choirs sometimes sing separately, sometimes together. The 'Sancta Maria' is again a point of simplification, but the sharpest contrast comes with the strongly rhythmical section beginning at "Ora pro nobis". 

Both settings are masterpieces. Ave Victoria!